P12529 [XJTUPC 2025] 对称隔离：黑白之战题解
LangHuo_25
·
·
题解
思路
非常巧妙的思路！
我们可以对于每块地毯进行分析，分为四种情况：
- 这块地毯是白的，邻近地毯有黑的，这块地毯只能是白。
- 这块地毯是黑的，邻近地毯全白的，这块地毯只能是黑。
- 这块地毯是白的，邻近地毯全白的，这块地毯可以由白变黑。
- 这块地毯是黑的，邻近地毯有黑的，一定无解。
我们将前三种情况的地毯分别标记为 0、1 和 2。
然后判断是否有可能存在竖直或水平对称轴。
对于竖直对称的两块地毯，如果存在两块地毯标记不相同，且都不是 2，那就不存在竖直对称轴。
水平对称同理。
正确性证明
这时候就有人要说了，这不是瞎写吗？假设两块相邻的地毯都由白变黑，这怎么办？
我们来分析一下：
现在有一块地毯 X_1，它有一块相邻的地毯 Y_1。
水平对称同理。
$X_1$ 和 $Y_1$ 不能都为黑。
那么 $X_2$ 和 $Y_2$ 都不能由白变黑。
相反同理。
所以只能是 $X_1$ 和 $Y_2$ 为黑，$X_2$ 和 $Y_1$ 为白，相反同理。
但是此时又不满足上面的假设了，$X_2$ 和 $Y_1$ 相邻的地毯有黑了，不能变色了。
所以这种思路是正确的。
# AC code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N][N],c[N][N];
string s;
int pd(int x,int y){
if(!c[x][y]){
if(c[x-1][y]|c[x][y-1]|c[x+1][y]|c[x][y+1]) return 0;
//这块地毯白，相邻的有黑
else return 2;//这块地毯白，相邻的地毯白
}
else return c[x-1][y]|c[x][y-1]|c[x+1][y]|c[x][y+1];
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s;
for(int j=1;j<=m;j++){
if(s[j-1]=='W') c[i][j]=0;
else c[i][j]=1;//标记颜色
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(pd(i,j)==1){//有相邻的黑色
cout<<"No";
return 0;
}
if(pd(i,j)==2) a[i][j]=2;//这块白地毯可改为黑色
else a[i][j]=c[i][j];//这块地毯不能改变颜色
}
}
//竖直对称轴
int vis=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!=a[i][m-j+1] && a[i][j]!=2 && a[i][m-j+1]!=2){
vis=1;//两块地毯颜色不同且无法改变颜色
break;
}
}
if(vis) break;
}
if(!vis){
cout<<"Yes";
return 0;
}
//水平对称轴
vis=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!=a[n-i+1][j] && a[i][j]!=2 && a[n-i+1][j]!=2){
vis=1;//两块地毯颜色不同且无法改变颜色
break;
}
}
if(vis) break;
}
if(!vis){
cout<<"Yes";
return 0;
}
cout<<"No";//两个对称轴都没有
}
```