填涂颜色
题目 填涂颜色
思路分析
即使圈长这样 也只需要一桶油漆就可以标记出来
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=35;
int g[N][N];
bool st[N][N];
int n;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=0 && x<=n-1 && y>=0 && y<=n-1 && !st[x][y];
}
void bfs(int x,int y){
queue<PII> q;
q.push({x,y});
st[x][y]=true;
while(!q.empty()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
for(int i=0;i<4;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny) && g[nx][ny]==0){
q.push({nx,ny});
st[nx][ny]=true;
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>g[i][j];
}
}
bfs(0,0);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(g[i][j]==0 && !st[i][j]){
g[i][j]=2;
}
cout<<g[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
发现出问题了
其实不能简单从0,0开始倒油漆
若00处是1的话 显然就有问题了
那在边框搜一圈 在边框发现0就倒颜料呢？
好像也不行 若最外圈都是1（即所有的0都在1里面） 就又不行了
那怎么办
没有办法就创作办法 没有0 我就自己在外面加一圈0呗
反正最后被1包住的0又不会受影响
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=35;
int g[N][N];
bool st[N][N];
int n;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y){//整个加一圈 数据在1~n 加上一圈0~n+1
return x>=0 && x<=n+1 && y>=0 && y<=n+1 && !st[x][y];
}
void bfs(int x,int y){
queue<PII> q;
q.push({x,y});
st[x][y]=true;
while(!q.empty()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
for(int i=0;i<4;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny) && g[nx][ny]==0){
q.push({nx,ny});
st[nx][ny]=true;
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>g[i][j];
}
}
bfs(0,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(g[i][j]==0 && !st[i][j]){
g[i][j]=2;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<g[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
💬 评论