Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- #include <cstdlib>
- #include <algorithm>
- #include <set>
- #include <queue>
- #include <stack>
- using namespace std;
- #define pb push_back
- #define mp make_pair
- #define x first
- #define y second
- typedef long long ll;
- typedef long double db;
- typedef pair <int, int> pii;
- typedef pair <db, db> pdd;
- const int X[8] = {1, 2, 2, 1, -1, -2, -2, -1};
- const int Y[8] = {2, 1, -1, -2, -2, -1, 1, 2};
- const int N = 20 + 1;
- vector < pair <pii, char> > a;
- vector <int> w[N];
- bool b[N];
- int mn = 100, n, m;
- bool can(char c, pii f, pii s)
- {
- if (c == 'K')
- return (max(abs(s.x - f.x), abs(s.y - f.y)) < 2);
- if (c == 'B')
- return ((s.y - s.x == f.y - f.x) || (s.y + s.x == f.y + f.x));
- if (c == 'R')
- return (s.x == f.x || s.y == f.y);
- if (c == 'Q')
- 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)));
- for (int i = 0; i < 8; i++)
- if (f.x + X[i] == s.x && f.y + Y[i] == s.y)
- return true;
- return false;
- }
- void brute(int x)
- {
- if (x == n)
- {
- for (int i = 0; i < n; i++)
- if (b[i])
- for (int j = 0; j < w[i].size(); j++)
- if (b[w[i][j]])
- return;
- int k = 0;
- for (int i = 0; i < n; i++)
- k += b[i];
- mn = min(n - k, mn);
- return;
- }
- b[x] = false;
- brute(x + 1);
- b[x] = true;
- brute(x + 1);
- }
- int main()
- {
- char c;
- cin >> n >> m;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++)
- {
- cin >> c;
- if (c != '.')
- a.pb(mp(mp(i, j), c));
- }
- n = a.size();
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- if (i == j)
- continue;
- else if (can(a[i].y, a[i].x, a[j].x))
- w[i].pb(j);
- brute(0);
- cout << mn << endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment