Madiyar

Untitled

May 28th, 2013
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <cassert>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <set>
  6. #include <map>
  7. #include <vector>
  8. #include <string>
  9. #include <cmath>
  10. #include <cstring>
  11. #include <queue>
  12. #include <stack>
  13. #include <algorithm>
  14. #include <sstream>
  15. #include <numeric>
  16. using namespace std;
  17.  
  18. #define f first
  19. #define s second
  20. #define mp make_pair
  21. #define sz(a) int((a).size())
  22. #define pb push_back
  23. #define all(c) (c).begin(),(c).end()
  24. #define forit(it,S) for(__typeof(S.begin()) it = S.begin(); it != S.end(); ++it)
  25. #ifdef WIN32
  26.     #define I64d "%I64d"
  27. #else
  28.     #define I64d "%lld"
  29. #endif
  30.  
  31. typedef long long ll;
  32. typedef vector <int> vi;
  33. typedef pair<int, int> pii;
  34. const int di[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
  35. const int dj[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
  36. char a[100][100];
  37. pii P[10000];
  38. pair<pii, int> q[10000000];
  39. int dist[16][16][40000];
  40. int n, m, R, C, Pn;
  41.  
  42. int sign(int x) {
  43.     if (x > 0) return 1;
  44.     if (x < 0) return -1;
  45.     return 0;
  46. }
  47. bool onAttack(int mask, int i, int j, int x, int y) {
  48.    
  49.     if (i == x && j == y) return false;
  50.    
  51.     if (a[i][j] == 'K') {
  52.         for (int k = 0; k < 8; ++k) {
  53.             int ii = i + di[k], jj = j + dj[k];
  54.             if (ii == x && jj == y) return true;
  55.         }  
  56.         return false;
  57.     } else if (a[i][j] == 'B') {
  58.    
  59.         if (i + j != x + y && i - j != x - y) return false;    
  60.        
  61.         for (int k = 0; k < Pn; ++k) if (mask & (1 << k)) {
  62.             int xx = P[k].f, yy = P[k].s;
  63.             if (xx == i && yy == j) continue;
  64.            
  65.             if ((i + j == x + y && i + j == xx + yy) || (i - j == x - y && i - j == xx - yy)) {
  66.                 if (abs(xx - i) < abs(x - i) && sign(xx - i) == sign(x - i) && sign(yy - j) == sign(y - j))
  67.                     return false;
  68.             }
  69.         }
  70.        
  71.         return true;
  72.     } else if (a[i][j] == 'R') {
  73.    
  74.         if (!(x == i || y == j)) return false;             
  75.        
  76.         for (int k = 0; k < Pn; ++k) if (mask & (1 << k)) {
  77.  
  78.             int xx = P[k].f, yy = P[k].s;
  79.            
  80.             if (xx == i && yy == j) continue;
  81.            
  82.             if (i == x && i == xx) {
  83.                 if (j < yy && yy < y) return false;
  84.                 if (y < yy && yy < j) return false;            
  85.             } else
  86.             if (j == y && j == yy) {
  87.                 if (i < xx && xx < x) return false;
  88.                 if (x < xx && xx < i) return false;
  89.             }  
  90.  
  91.         }
  92.         return true;
  93.     }
  94.     assert(false);
  95.  
  96. }
  97.  
  98. int main() {
  99.  
  100.     scanf("%d%d", &n, &m);
  101.     for (int i = 0; i < n; ++i) {
  102.         scanf("\n");
  103.         for (int j = 0; j < m; ++j) {
  104.             scanf("%c", &a[i][j]);
  105.    
  106.             if (a[i][j] == '*') {
  107.                 R = i; C = j;
  108.             } else
  109.             if (a[i][j] != '.') {
  110.                 P[Pn++] = mp(i, j);
  111.             }
  112.         }
  113.     }
  114.  
  115.     int head = 0, tail = 0;
  116.     q[tail++] = mp(mp(R, C), (1 << Pn) - 1);
  117.     dist[R][C][(1 << Pn) - 1] = 1;
  118.    
  119.     while (head != tail) {
  120.         int mask = q[head].s;
  121.         int i = q[head].f.f;
  122.         int j = q[head++].f.s;
  123.  
  124.         if (mask == 0) {
  125.             printf("%d\n", dist[i][j][mask] - 1);
  126.             return 0;
  127.         }
  128.        
  129.         for (int di = -1; di <= 1; ++di)
  130.             for (int dj = -1; dj <= 1; dj++) if (di != 0 || dj != 0) {
  131.                 int x = di + i, y = dj + j;
  132.                
  133.                 if (!(0 <= x && x < n && 0 <= y && y < m)) continue;
  134.                
  135.                 bool ok = true;
  136.                 for (int k = 0; ok && k < Pn; ++k)
  137.                     if ((mask & (1 << k)) && onAttack(mask, P[k].f, P[k].s, x, y)) ok = false;
  138.  
  139.                
  140.                 if (!ok) continue;     
  141.                
  142.                 int nmask = mask;
  143.                 for (int k = 0; k < Pn; ++k)
  144.                     if (mp(x, y) == P[k]) {
  145.                         if (nmask & (1 << k)) nmask ^= (1 << k);
  146.                         break;
  147.                     }
  148.                    
  149.                 if (!dist[x][y][nmask]) {
  150.                     dist[x][y][nmask] = dist[i][j][mask] + 1;
  151.                     q[tail++]= mp(mp(x, y), nmask);
  152.                 }  
  153.             }
  154.            
  155.     }
  156.     puts("-1");
  157.     return 0;      
  158. }
Advertisement
Add Comment
Please, Sign In to add comment