Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define int long long
- #define all(x) (x).begin(), (x).end()
- using namespace std;
- const int N = 15;
- const int dx[4] = {0, 0, 1, -1};
- const int dy[4] = {1, -1, 0, 0};
- int n;
- int id[N][N], is[N][N], used[N][N];
- char a[N][N];
- int grundy[(1<<21)];
- bool good(int x, int y) {
- if (x < 1 || y < 1 || x > n || y > n || used[x][y] || a[x][y] != '.')
- return 0;
- bool can = 0;
- for (int i = 0; i < 4; i++)
- if (a[x + dx[i]][y + dy[i]] == '*')
- can = 1;
- return can;
- }
- vector<pair<int, int> > c;
- void dfs(int x, int y) {
- used[x][y] = 1;
- c.pb({x, y});
- for (int i = 0; i < 4; i++)
- if (good(x + dx[i], y + dy[i]))
- dfs(x + dx[i], y + dy[i]);
- }
- int solve(int mask) {
- if (grundy[mask] != -1)
- return grundy[mask];
- if (mask == 0)
- return grundy[mask] = 0;
- vector<int> q;
- for (int i = 0; i < c.size(); i++)
- if (is[c[i].first][c[i].second]) {
- int nmask = mask;
- vector<pair<int, int> > removed;
- int x = c[i].first, y = c[i].second;
- is[x][y] = 0;
- nmask ^= (1 << id[x][y]);
- removed.pb({x, y});
- for (int d = 0; d < 4; d++)
- if (is[x + dx[d]][y + dy[d]]) {
- nmask ^= (1 << id[x + dx[d]][y + dy[d]]);
- is[x + dx[d]][y + dy[d]] = 0;
- removed.pb({x + dx[d], y + dy[d]});
- }
- q.pb(solve(nmask));
- for (auto [x, y] : removed)
- is[x][y] = 1;
- }
- sort(all(q));
- if (q[0] != 0)
- return grundy[mask] = 0;
- for (int i = 1; i < q.size(); i++)
- if (q[i] != q[i - 1] && q[i] != q[i - 1] + 1)
- return (grundy[mask] = q[i - 1] + 1);
- return grundy[mask] = q.back() + 1;
- }
- signed main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin >> n;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- cin >> a[i][j];
- int ans = 0;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- if (good(i, j)) {
- c.clear();
- dfs(i, j);
- for (int k = 0; k < c.size(); k++)
- id[c[k].first][c[k].second] = k, is[c[k].first][c[k].second] = 1;
- for (int k = 0; k < (1 << c.size()); k++)
- grundy[k] = -1;
- ans ^= solve((1 << c.size()) - 1);
- for (int k = 0; k < c.size(); k++)
- id[c[k].first][c[k].second] = 0, is[c[k].first][c[k].second] = 0;
- }
- cout << (ans != 0 ? "First player will win" : "Second player will win");
- return 0;
- }
RAW Paste Data