/** * CERC 2018 * Problem Solution: The Lord of the Kings * Idea: Find Steiner tree of particular graph * @author Josef Malik */ #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int ll; typedef pair pii; #define PB push_back #define MP make_pair #define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++) #define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--) #define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--) #define R1(a) do{scanf("%d", &(a));}while(0) #define R2(a, b) do{scanf("%d%d", &(a), &(b));}while(0) #define R3(a, b, c) do{scanf("%d%d%d", &(a), &(b), &(c));}while(0) #define SV(vec) do{int s_v_;scanf("%d", &(s_v_));vec.PB(s_v_);}while(0) #define MM(co, cim) memset((co), (cim), sizeof((co))) #define DEB(x) cerr << ">>> " << #x << " : " << x << endl; #define INF 100000007 #define MAXS 16 #define MAXT 11 int km[][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}}; int n, m, sx, sy, t, ts, vcnt; char c; int d[MAXS*MAXS][MAXS*MAXS]; vector terms; int dp[MAXS*MAXS][1 << MAXT]; int gv (int x, int y) { return x * m + y; } int isv (int x, int y) { return (x >= 0 && x < n && y >= 0 && y < m); } int main () { //load grid structure R2(n, m); vcnt = n * m; FOR(i, 0, vcnt) FOR(j, 0, vcnt) d[i][j] = INF; FOR(i, 0, vcnt) d[i][i] = 0; //load terminals R2(sx, sy); --sx;--sy; terms.PB(gv(sx, sy)); scanf(" %c", &c); R1(t); FOR(i, 0, t) { int x, y; R2(x, y); --x;--y; terms.PB(gv(x, y)); if (c == 'B' && ((sx + sy) % 2) != ((x + y) % 2)) { printf("-1\n"); return 0; } } ts = terms.size(); //translate grid->graph if (c == 'K') { FOR(i, 0, n) FOR(j, 0, m) { FOR(di, -1, 2) FOR(dj, -1, 2) if (isv(i + di, j + dj)) { int x = gv(i,j); int y = gv(i + di, j + dj); if (x != y) d[x][y] = d[y][x] = 1; } } } else if (c == 'R') { FOR(i, 0, n) FOR(j, 0, m) { FOR(di, -1, 2) FOR(dj, -1, 2) if (di * di + dj * dj == 1) { int cm = 0; while (isv(i + di * cm, j + dj * cm)) { int x = gv(i,j); int y = gv(i + di * cm, j + dj * cm); if (x != y) d[x][y] = d[y][x] = 1; ++cm; } } } } else if (c == 'Q') { FOR(i, 0, n) FOR(j, 0, m) { FOR(di, -1, 2) FOR(dj, -1, 2) if (di * di + dj * dj > 0) { int cm = 0; while (isv(i + di * cm, j + dj * cm)) { int x = gv(i,j); int y = gv(i + di * cm, j + dj * cm); if (x != y) d[x][y] = d[y][x] = 1; ++cm; } } } } else if (c == 'B') { FOR(i, 0, n) FOR(j, 0, m) { FOR(di, -1, 2) FOR(dj, -1, 2) if (di * di + dj * dj > 1) { int cm = 0; while (isv(i + di * cm, j + dj * cm)) { int x = gv(i,j); int y = gv(i + di * cm, j + dj * cm); if (x != y) d[x][y] = d[y][x] = 1; ++cm; } } } } else { FOR(i, 0, n) FOR(j, 0, m) { FOR(k, 0, 8) if (isv(i + km[k][0], j + km[k][1])) { int x = gv(i,j); int y = gv(i + km[k][0], j + km[k][1]); if (x != y) d[x][y] = d[y][x] = 1; } } } //fw FOR(k, 0, vcnt) FOR(i, 0, vcnt) FOR(j, 0, vcnt) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); //steiner FOR(i, 0, vcnt) FOR(j, 0, 1 << ts) dp[i][j] = INF; FOR(i, 0, ts) dp[terms[i]][1 << i] = 0; FOR(mask, 0, 1 << ts) { FOR(i, 0, vcnt) { for (int submask = mask; submask > 0; submask = (submask - 1) & mask) { dp[i][mask] = min(dp[i][mask], dp[i][submask] + dp[i][mask - submask]); } FOR(j, 0, vcnt) dp[j][mask] = min(dp[j][mask], dp[i][mask] + d[i][j]); } } //get result int res = dp[gv(sx, sy)][(1 << ts) - 1]; printf("%d\n", res < INF ? res : -1); return 0; }