Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cassert>
- #include <cstdio>
- #include <cstdlib>
- #include <set>
- #include <map>
- #include <vector>
- #include <string>
- #include <cmath>
- #include <cstring>
- #include <queue>
- #include <stack>
- #include <algorithm>
- #include <sstream>
- #include <numeric>
- using namespace std;
- #define f first
- #define s second
- #define mp make_pair
- #define sz(a) int((a).size())
- #define pb push_back
- #define all(c) (c).begin(),(c).end()
- #define forit(it,S) for(__typeof(S.begin()) it = S.begin(); it != S.end(); ++it)
- #ifdef WIN32
- #define I64d "%I64d"
- #else
- #define I64d "%lld"
- #endif
- typedef long long ll;
- typedef vector <int> vi;
- typedef pair<int, int> pii;
- const int di[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
- const int dj[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
- char a[100][100];
- pii P[10000];
- pair<pii, int> q[10000000];
- int dist[16][16][40000];
- int n, m, R, C, Pn;
- int sign(int x) {
- if (x > 0) return 1;
- if (x < 0) return -1;
- return 0;
- }
- bool onAttack(int mask, int i, int j, int x, int y) {
- if (i == x && j == y) return false;
- if (a[i][j] == 'K') {
- for (int k = 0; k < 8; ++k) {
- int ii = i + di[k], jj = j + dj[k];
- if (ii == x && jj == y) return true;
- }
- return false;
- } else if (a[i][j] == 'B') {
- if (i + j != x + y && i - j != x - y) return false;
- for (int k = 0; k < Pn; ++k) if (mask & (1 << k)) {
- int xx = P[k].f, yy = P[k].s;
- if (xx == i && yy == j) continue;
- if ((i + j == x + y && i + j == xx + yy) || (i - j == x - y && i - j == xx - yy)) {
- if (abs(xx - i) < abs(x - i) && sign(xx - i) == sign(x - i) && sign(yy - j) == sign(y - j))
- return false;
- }
- }
- return true;
- } else if (a[i][j] == 'R') {
- if (!(x == i || y == j)) return false;
- for (int k = 0; k < Pn; ++k) if (mask & (1 << k)) {
- int xx = P[k].f, yy = P[k].s;
- if (xx == i && yy == j) continue;
- if (i == x && i == xx) {
- if (j < yy && yy < y) return false;
- if (y < yy && yy < j) return false;
- } else
- if (j == y && j == yy) {
- if (i < xx && xx < x) return false;
- if (x < xx && xx < i) return false;
- }
- }
- return true;
- }
- assert(false);
- }
- int main() {
- scanf("%d%d", &n, &m);
- for (int i = 0; i < n; ++i) {
- scanf("\n");
- for (int j = 0; j < m; ++j) {
- scanf("%c", &a[i][j]);
- if (a[i][j] == '*') {
- R = i; C = j;
- } else
- if (a[i][j] != '.') {
- P[Pn++] = mp(i, j);
- }
- }
- }
- int head = 0, tail = 0;
- q[tail++] = mp(mp(R, C), (1 << Pn) - 1);
- dist[R][C][(1 << Pn) - 1] = 1;
- while (head != tail) {
- int mask = q[head].s;
- int i = q[head].f.f;
- int j = q[head++].f.s;
- if (mask == 0) {
- printf("%d\n", dist[i][j][mask] - 1);
- return 0;
- }
- for (int di = -1; di <= 1; ++di)
- for (int dj = -1; dj <= 1; dj++) if (di != 0 || dj != 0) {
- int x = di + i, y = dj + j;
- if (!(0 <= x && x < n && 0 <= y && y < m)) continue;
- bool ok = true;
- for (int k = 0; ok && k < Pn; ++k)
- if ((mask & (1 << k)) && onAttack(mask, P[k].f, P[k].s, x, y)) ok = false;
- if (!ok) continue;
- int nmask = mask;
- for (int k = 0; k < Pn; ++k)
- if (mp(x, y) == P[k]) {
- if (nmask & (1 << k)) nmask ^= (1 << k);
- break;
- }
- if (!dist[x][y][nmask]) {
- dist[x][y][nmask] = dist[i][j][mask] + 1;
- q[tail++]= mp(mp(x, y), nmask);
- }
- }
- }
- puts("-1");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment