My Blogs
P10543 [THUPC2024] 黑白
签到题。
首先要判联通性。判完之后，统计全局的白格子个数 $s$。
因为删到最后，一定会留下一条白色路径，然后路径的长度在 $\bmod\;2$ 意义下和 $n+m-1$ 同余。而我们只关心能操作次数的奇偶性，所以只需要判断 $s-n-m$ 的奇偶性即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int T,n,m,s;
bitset<1010> v[1010],v2[1010];
char c[1010];
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void dfs(int x,int y)
{
v2[x][y]=1;
for(int i=0;i<4;++i)
{
int xx=dx[i]+x,yy=dy[i]+y;
if(xx>0&&yy>0&&xx<=n&&yy<=m&&v[xx][yy]&&!v2[xx][yy])
dfs(xx,yy);
}
}
inline void mian()
{
cin>>T;
while(T--)
{
cin>>n>>m,s=0;
for(int i=1;i<=n;++i)
{
v2[i].reset(),scanf("%s",c+1);
for(int j=1;j<=m;++j)
v[i][j]=c[j]=='W',s+=v[i][j];
}
dfs(1,1);
if(!v2[n][m]){puts("J");continue;}
if((s-n-m)&1)puts("J");
else puts("I");
}
}