跳过正文
题解:AT_past202203_f 地図の塗り分け

题解:AT_past202203_f 地図の塗り分け

xyx404
作者
xyx404
Have a nice day.

思路:
#

遍历每个点,查看点的右方和下方,如果两个点分属不同的州且颜色相同输出 No 并结束程序,否则继续遍历,为什么不用查看上方和下方呢,因为我们是按顺序遍历的从左到右,从上到下,在遍历的过程中已经确认这个点和这个点的上方和左方符合条件了。

遍历完后输出 Yes

代码:
#

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int h,w,n,jz[210][210],c[500];
int dx[]={0,1},dy[]={1,0};
int main(){
	memset(jz,0,sizeof(jz));
	cin>>h>>w>>n;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++)cin>>jz[i][j];
	}
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			int tampx,tampy;
			tampx=dx[0]+i,tampy=dy[0]+j;
			if(jz[tampx][tampy]!=jz[i][j]){
				if(c[jz[tampx][tampy]]==c[jz[i][j]]){
					cout<<"No\n";return 0;
				}
			}
			tampx=dx[1]+i,tampy=dy[1]+j;
			if(jz[tampx][tampy]!=jz[i][j]){
				if(c[jz[tampx][tampy]]==c[jz[i][j]]){
					cout<<"No\n";return 0;
				}
			}
		}
	}
	cout<<"Yes\n";
	return 0;
}