填涂颜色
作者:
AC就喝AD钙
,
2024-03-27 00:38:08
,
所有人可见
,
阅读 10
//题目地址:https://www.luogu.com.cn/problem/P1162
//想着不能太摆烂就来水一题叭
//填涂颜色问题
//边界处理 + BFS
#include<bits/stdc++.h>
#define endl '\n'
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 35;
int n;
int g[N][N];
bool st[N][N];
queue<PII> q;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
void bfs(int x1, int y1)
{
q.push({x1, y1});
st[x1][y1] = true;
while(!q.empty())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i ++)
{
int a = t.x + dx[i];
int b = t.y + dy[i];
if(a < 0 || a > n + 1 || b < 0 || b > n + 1) continue;
if(g[a][b] == 1) continue;
if(st[a][b]) continue;
st[a][b] = true;
q.push({a, b});
}
}
return ;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
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;
}
cout<<g[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
有点类似前几天的Flood Fill连通块