n ∗ m的迷宫,有很多障碍,只有清理了外围的障碍,才能清理内部的。两个人轮留清理外围的障碍。最后轮到谁清理,对方可以直接走到宝藏,则谁赢。
这个题目分两步
第一步,判断宝藏是不是直接就可以被拿~
第二步,统计障碍的个数,如果是偶数后手必胜,如果是奇数,先手必胜(最后的末状态一定是宝藏周围3个障碍)。
最后的状态假设是到达终点的连通块四周全是1
剩下都障碍数都用ans来统计,ans是奇数,那么让对方破除最后一个障碍,我方拿到宝藏
如果ans是偶数,我方后手来选,仍可以让对方破除障碍,我方拿到宝藏
核心就是分离出终点连通块周边全为1的状态,根据ans的奇数偶数就可以得到答案
#include <bits/stdc++.h>
using namespace std;
#define mset(s, _) memset(s, _, sizeof(s))
#define rint register int
const int N = 302;
int a[N][N];
int n, m;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int vis[N][N];
queue <pair <int, int>> q;
bool bfs(int px, int py) {
while (!q.empty()) q.pop();
q.push(make_pair(px, py));
mset(vis, 0);
vis[px][py] = 1;
while (!q.empty()) {
pair <int, int> u = q.front(); q.pop();
for (rint d = 0; d < 4; d++) {
int fx = u.first + dx[d], fy = u.second + dy[d];
if (fx >= 1 && fx <= n && fy >= 1 && fy <= m && !vis[fx][fy] && a[fx][fy] <= 0) {
vis[fx][fy] = 1;
q.push(make_pair(fx, fy));
}
}
}
for (rint i = 1; i <= n; i++) {
for (rint j = 1; j <= m; j++) {
//printf("vis[%d][%d] = %d\n", i, j, vis[i][j]);
if (vis[i][j] && (i == 1 || i == n || j == 1 || j == m)) {
return 1;
}
}
}
return 0;
}
int main() {
int T; cin >> T;
while (T--) {
scanf("%d%d", &n, &m);
int ans = 0, px, py;
for (rint i = 1; i <= n; i++) {
for (rint j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
if (a[i][j] == -1) {
px = i, py = j;
} else {
ans += a[i][j];
}
}
}
if (bfs(px, py)) {
puts("JM First");
continue;
}
for (rint i = 1; i <= n; i++) {
for (rint j = 1; j <= m; j++) {
if (!vis[i][j] && (vis[i - 1][j] || vis[i + 1][j] || vis[i][j - 1] || vis[i][j + 1])) {
ans--;
}
}
}
if (ans & 1) {
puts("JM First");
} else {
puts("JM Second");
}
}
return 0;
}