专栏文章

P12529 [XJTUPC 2025] 对称隔离:黑白之战题解

P12529题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip9e24f
此快照首次捕获于
2025/12/03 08:18
3 个月前
此快照最后确认于
2025/12/03 08:18
3 个月前
查看原文

思路

非常巧妙的思路!
我们可以对于每块地毯进行分析,分为四种情况:
  • 这块地毯是白的,邻近地毯有黑的,这块地毯只能是白。
  • 这块地毯是黑的,邻近地毯全白的,这块地毯只能是黑。
  • 这块地毯是白的,邻近地毯全白的,这块地毯可以由白变黑。
  • 这块地毯是黑的,邻近地毯有黑的,一定无解。
我们将前三种情况的地毯分别标记为 001122
然后判断是否有可能存在竖直或水平对称轴。
对于竖直对称的两块地毯,如果存在两块地毯标记不相同,且都不是 22,那就不存在竖直对称轴。
水平对称同理。

正确性证明

这时候就有人要说了,这不是瞎写吗?假设两块相邻的地毯都由白变黑,这怎么办?
我们来分析一下:
现在有一块地毯 X1X_1,它有一块相邻的地毯 Y1Y_1
X1X_1 竖直对称的地毯为 X2X_2Y1Y_1 竖直对称的地毯为 Y2Y_2
水平对称同理。
X1X_1Y1Y_1 不能都为黑。
那么 X2X_2Y2Y_2 都不能由白变黑。
相反同理。
所以只能是 X1X_1Y2Y_2 为黑,X2X_2Y1Y_1 为白,相反同理。
但是此时又不满足上面的假设了,X2X_2Y1Y_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";//两个对称轴都没有 
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...