专栏文章
P12529 [XJTUPC 2025] 对称隔离:黑白之战题解
P12529题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mip9e24f
- 此快照首次捕获于
- 2025/12/03 08:18 3 个月前
- 此快照最后确认于
- 2025/12/03 08:18 3 个月前
思路
非常巧妙的思路!
我们可以对于每块地毯进行分析,分为四种情况:
- 这块地毯是白的,邻近地毯有黑的,这块地毯只能是白。
- 这块地毯是黑的,邻近地毯全白的,这块地毯只能是黑。
- 这块地毯是白的,邻近地毯全白的,这块地毯可以由白变黑。
- 这块地毯是黑的,邻近地毯有黑的,一定无解。
我们将前三种情况的地毯分别标记为 、 和 。
然后判断是否有可能存在竖直或水平对称轴。
对于竖直对称的两块地毯,如果存在两块地毯标记不相同,且都不是 ,那就不存在竖直对称轴。
水平对称同理。
正确性证明
这时候就有人要说了,这不是瞎写吗?假设两块相邻的地毯都由白变黑,这怎么办?
我们来分析一下:
现在有一块地毯 ,它有一块相邻的地毯 。
竖直对称的地毯为 , 竖直对称的地毯为 。
水平对称同理。
和 不能都为黑。
那么 和 都不能由白变黑。
相反同理。
所以只能是 和 为黑, 和 为白,相反同理。
但是此时又不满足上面的假设了, 和 相邻的地毯有黑了,不能变色了。
所以这种思路是正确的。
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";//两个对称轴都没有
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...