You've successfully subscribed to ムえのBLOG
Great! Next, complete checkout for full access to ムえのBLOG
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.

题解 P1162 【填涂颜色】

. 2 min read

BFS

非常明白的BFS 唯一要判断的就是  圈内圈外

也不难证明圈内的 "$0$" 点一定会有在其上下左右都有"$1$" 点

这就是搜索起点的判断条件

上代码:

#include <iostream>
#include <queue>
#include <algorithm>
#define MAX 35
using namespace std;
int n;
int map[MAX][MAX];
//bool vis[MAX][MAX]={0};
struct point{
	int x,y;
};
queue<point> q;
int walk[4][2]={1,0,-1,0,0,1,0,-1};
//朴素的BFS↓
void bfs(point a){
	q.push(a);
	map[a.x][a.y]=2;
	while (!q.empty()){
		point now,next;
		now=q.front();q.pop();
		for (int i=0;i<4;i++){
			int xx=now.x+walk[i][0];
			int yy=now.y+walk[i][1];
			if (xx>0&&yy>0&&xx<=n&&yy<=n&&map[xx][yy]==0){//判断边界和vis因为更新map为2所以在map上判断就可以了
				next.x=xx;next.y=yy;
				map[xx][yy]=2;
				q.push(next);
			}
		}
	}
	return;
}
//判断圈内函数↓
bool incyc(point a){
    if (map[a.x][a.y]==1) return 0;
	bool f1,f2,f3,f4;
	f1=f2=f3=f4=0;
    //上下左右是否都有一
	for (register int i=a.x;i>=1;i--)
	if (map[i][a.y]==1) {f1=1;break;}
	for (register int i=a.x;i<=n;i++)
	if (map[i][a.y]==1) {f2=1;break;}
	for (register int i=a.y;i>=1;i--)
	if (map[a.x][i]==1) {f3=1;break;}
	for (register int i=a.y;i<=n;i++)
	if (map[a.x][i]==1) {f4=1;break;}
	if (f1==1&&f2==1&&f3==1&&f4==1) return 1;
	return 0;
}
int main(){
	cin>>n;
	for (register int i=1;i<=n;i++)for (register int j=1;j<=n;j++)cin>>map[i][j];
	for (register int i=1;i<=n;i++)for (register int j=1;j<=n;j++){//构建起始点
		point k;k.x=i;k.y=j;
		if (incyc(k)){
			bfs(k);
			for (register int i=1;i<=n;i++){for (register int j=1;j<=n;j++)cout<<map[i][j]<<" ";cout<<endl;}//输出
	return 0;
		}
	}
}


本站总访问量 正在加载今日诗词....