Guest User

Untitled

a guest
Dec 15th, 2018
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <cstdlib>
  5. #include <algorithm>
  6. #include <set>
  7. #include <queue>
  8. #include <stack>
  9.  
  10. using namespace std;
  11.  
  12. #define pb push_back
  13. #define mp make_pair
  14. #define x first
  15. #define y second
  16.  
  17. typedef long long ll;
  18. typedef long double db;
  19. typedef pair <int, int> pii;
  20. typedef pair <db, db> pdd;
  21.  
  22. const int X[8] = {1, 2,  2,  1, -1, -2, -2, -1};
  23. const int Y[8] = {2, 1, -1, -2, -2, -1,  1,  2};
  24. const int N = 20 + 1;
  25.  
  26. vector < pair <pii, char> > a;
  27. vector <int> w[N];
  28. bool b[N];
  29. int mn = 100, n, m;
  30.  
  31. bool can(char c, pii f, pii s)
  32. {
  33.   if (c == 'K')
  34.     return (max(abs(s.x - f.x), abs(s.y - f.y)) < 2);
  35.   if (c == 'B')
  36.     return ((s.y - s.x == f.y - f.x) || (s.y + s.x == f.y + f.x));
  37.   if (c == 'R')
  38.     return (s.x == f.x || s.y == f.y);
  39.   if (c == 'Q')
  40.     return ((s.x == f.x || s.y == f.y) || ((s.y - s.x == f.y - f.x) || (s.y + s.x == f.y + f.x)));
  41.  
  42.   for (int i = 0; i < 8; i++)
  43.     if (f.x + X[i] == s.x && f.y + Y[i] == s.y)
  44.       return true;
  45.   return false;
  46. }
  47.  
  48. void brute(int x)
  49. {
  50.   if (x == n)
  51.   {
  52.     for (int i = 0; i < n; i++)
  53.       if (b[i])
  54.         for (int j = 0; j < w[i].size(); j++)
  55.           if (b[w[i][j]])
  56.             return;
  57.     int k = 0;
  58.     for (int i = 0; i < n; i++)
  59.       k += b[i];
  60.     mn = min(n - k, mn);
  61.     return;
  62.   }
  63.  
  64.   b[x] = false;
  65.   brute(x + 1);
  66.   b[x] = true;
  67.   brute(x + 1);
  68. }
  69.  
  70. int main()
  71. {
  72.   char c;
  73.  
  74.   cin >> n >> m;
  75.  
  76.   for (int i = 0; i < n; i++)
  77.     for (int j = 0; j < m; j++)
  78.     {
  79.       cin >> c;
  80.       if (c != '.')
  81.         a.pb(mp(mp(i, j), c));
  82.     }
  83.   n = a.size();
  84.   for (int i = 0; i < n; i++)
  85.     for (int j = 0; j < n; j++)
  86.       if (i == j)
  87.         continue;
  88.       else if (can(a[i].y, a[i].x, a[j].x))
  89.         w[i].pb(j);
  90.  
  91.   brute(0);
  92.   cout << mn << endl;
  93.  
  94.   return 0;
  95. }
Add Comment
Please, Sign In to add comment