洛谷 4959. bfs+染色,爆搜训练
原题链接
中等
作者:
可能永远ac不了吧
,
2023-05-27 16:11:32
,
所有人可见
,
阅读 142
题目描述
染色法bfs
参考文献
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>PII;
const int N=40;
int a[N][N];
bool st[N][N];
int n;
int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
queue<PII>q;
int main(){
cin>>n;
memset(a,0,sizeof a);
memset(st,0,sizeof st);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)cin>>a[i][j];
q.push({1,1});
while(q.size()){
auto t=q.front();
q.pop();
for(int i=0;i<4;i++){
int x=t.first+dx[i],y=t.second+dy[i];
if(x>=1&&x<=n&&y>=1&&y<=n&&a[x][y]==0){
a[x][y]=2;
q.push({x,y});
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<2-a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}