/** * CERC 2018 * Problem Solution: Lord of the Kings * * @author Josef Cibulka */ #include #include #include #include #include #include #include #include #include #define DEB 0 #define MAXTERM 12 #define MAXDIM 16 using namespace std; int n, m; int vid(int r, int c) { if(r<0 || r>=n || c<0 || c>=m) return -1; return r * m + c; } class Graph { public: int vcnt; vector> neighs; vector terms; vector> best_sol; vector> known_dsts; explicit Graph(int vcnt_) : vcnt(vcnt_), neighs(vcnt_, vector()), known_dsts(vcnt_, vector(vcnt_, -2)) { } int count_dst(int u, int v) { #if(DEB) cout << "dst: " << u << " " << v; #endif if(u==v) return 0; if(known_dsts[u][v] > -2) return known_dsts[u][v]; deque q; vector dst(vcnt, -1); q.push_back(u); dst[u] = 0; while(q.size() > 0) { int fr = q.front(); q.pop_front(); for(int t : neighs[fr]) { if(dst[t] >= 0) continue; dst[t] = dst[fr] + 1; q.push_back(t); #if(DEB) if(t == v) cout << dst[t] << endl; #endif if(t == v) { known_dsts[u][v] = dst[t]; return dst[t]; } } } known_dsts[u][v] = -1; return -1; } vector subsub(vector& sub, int ind) { vector ret; // cout << "ind: " << ind; for(char b : sub) { if(!b) { ret.push_back(b); } else { char newb = (ind&1); ind >>= 1; // cout << "indred: " << ind << " newb: " << newb << " "; ret.push_back(newb); } } return ret; } int subind(vector& sub) { int ret = 0; for(char b : sub) ret = ((ret<<1) + b); return ret; } int vecsize(vector& sub) { int ret = 0; for(char b : sub) ret += b; return ret; } int solve(vector& sub, int root, bool toplevel) { #if(DEB) cout << "subind: " << subind(sub) << " root: " << root << endl; #endif int known = best_sol[subind(sub)][root]; if(known != -2) { // cout << "Known " << known << endl; return known; } int subsize = 0; int member = -1; for (size_t i = 0; i < sub.size(); ++i) if(sub[i]) { ++subsize; member = i; } // cout << "sub " << subsize << endl; if(subsize == 1) { int sol = 1; if(root != terms[member]) { int dst = count_dst(terms[member], root); if(dst == -1) sol = -1; else sol = dst + 1; } // cout << "sol: " << sol << endl; best_sol[subind(sub)][root] = sol; return sol; } int best = -1; for(int i = 1; i < (1< icompl) continue; vector suba = subsub(sub, i); vector subb = subsub(sub, icompl); for(int root2 = 0; root2 < vcnt; ++root2) { if(toplevel && root!=root2) continue; #if(DEB) cout << "suba: "; for (int i = 0; i < suba.size(); ++i) cout << suba[i]; cout << endl; #endif int cura = solve(suba, root2, false); int curb = solve(subb, root2, false); int dst = count_dst(root, root2); if (cura == -1 || curb == -1 || dst == -1) continue; int cur = cura + curb + dst - 1; // cout << "root " << root << " root2 " << root2 << " "; // cout << "cura " << cura << " curb " << curb << " dst " << dst << " cur: " << cur << endl; if(best == -1 || (cur != -1 && cur < best)) best = cur; } } #if(DEB) cout << "root " << root << " "; for(int i = 0; i < sub.size(); ++i) if(sub[i]) cout << terms[i] << " "; cout << " best : " << best << endl; #endif best_sol[subind(sub)][root] = best; return best; } int steiner(vector terms_) { terms = terms_; best_sol.resize(1<(vcnt, -2)); vector sub(terms.size(), true); int best = -1; for(int root = 0; root < vcnt; ++root) { int cur = solve(sub, root, true); if(best == -1 || (cur != -1 && cur < best)) best = cur; } return best; } }; Graph build(int type) { Graph g(n*m); for (int r = 0; r < n; ++r) for (int c = 0; c < m; ++c) { int id = vid(r,c); if(type == 'K') { for(int i=-1; i<=1; ++i) for(int j=-1; j<=1; ++j) { if (i==0 && j==0) continue; int nid = vid(r + i, c + j); if(nid != -1) g.neighs[id].push_back(nid); } } if(type == 'N') { for(int i=-2; i<=2; ++i) for(int j=-2; j<=2; ++j) { if (i==0 || j==0 || abs(i) == abs(j)) continue; int nid = vid(r + i, c + j); if(nid != -1) g.neighs[id].push_back(nid); } } if(type == 'B' || type == 'Q') { for(int i=-n; i<=n; ++i) for(int j : vector {-i, i}) { if (i==0) continue; int nid = vid(r + i, c + j); if(nid != -1) g.neighs[id].push_back(nid); } } if(type == 'R' || type == 'Q') { for(int i=-n; i<=n; ++i) { if (i==0) continue; int nid = vid(r + i, c); if(nid != -1) g.neighs[id].push_back(nid); } for(int j=-m; j<=m; ++j) { if (j==0) continue; int nid = vid(r, c + j); if(nid != -1) g.neighs[id].push_back(nid); } } // cout << "(" << r << ", " << c << "):" << g.neighs[id].size() << endl; } return g; } int main(void) { cin >> n >> m; int r, c; char type; cin >> r >> c >> type; vector terms; terms.push_back(vid(r-1, c-1)); int ccnt; cin >> ccnt; for (int i = 0; i < ccnt; ++i) { cin >> r >> c; terms.push_back(vid(r-1, c-1)); } Graph g = build(type); int res = g.steiner(terms); if(res != -1) --res; cout << res << endl; return 0; }