好题。
题意
\(n\times m\) 的网格图初始每个格子有黑有白，两人轮流操作，每次选择一个白格染黑。操作后不能存在一条 \((1,1)\) 到 \((n,m)\) 的路径，否则本次操作者输，另一人赢。
思路
首先判断是否一上来就输了。
易发现到最后一定会操作到只剩一条道路，设路径长度为 \(s\)，那么 \(s\) 的奇偶性一定和 \(n+m-1\) 奇偶性一样，而我们只要知道 \(s\) 的奇偶性就可求出答案。
AC Code
#include<bits/stdc++.h>
using namespace std;
int t,n,m,s;
string c;
bitset <1010>v[1010],w[1010];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void dfs(int x,int y){
w[x][y]=1;
for(int i=0;i<4;i++){
int xa=dx[i]+x,ya=dy[i]+y;
if(xa>0&&ya>0&&xa<=n&&ya<=m&&v[xa][ya]&&!w[xa][ya])dfs(xa,ya);
}
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
s=0;
for(int i=1;i<=n;i++){
w[i].reset();
cin>>c;
for(int j=1;j<=m;j++)v[i][j]=c[j-1]=='W',s+=v[i][j];
}
dfs(1,1);
if(!w[n][m]){cout<<"J\n";continue;}
if((s-n-m)&1)cout<<"J";
else cout<<"I";
puts("");
}
return 0;
}