题目描述
由数字0 组成的方阵中，可能有若干任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6X6的方阵（n=6），涂色前和涂色后的方阵如下：
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
如果没有闭合圈，则涂色前后方阵相同。
输入格式：
每组测试数据第一行一个整数：n。其中n(1<=n<=30)
接下来n行，由0和1组成的nXn的方阵。
方阵内只有一个闭合圈，圈内至少有一个0。
输出格式：
已经填好数字2的完整方阵。
输入样例#1：
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
输出样例#1：
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
提示
1≤n≤30
填涂颜色问题该咋写啊
对于这种问题多多考虑搜索算法（例如DFS和BFS），利用他们来找到需要填充的区域，并将其标记为已经填充。具体来说，可以从给定的起点开始进行搜索，如果遇到了需要填充的区域，就将其标记为已经填充，并继续向周围的区域进行搜索，直到所有需要填充的区域都被找到并标记为已经填充为止。
#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define mod 1000000007
#define ll long long
#define ull unsigned long long
#define mem(a) memset(a,0,sizeof(a))
#define cio ios::sync_with_stdio(false);
int next[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int n;
int s[35][35];
int vis[35][35];
struct node
{
int x, y;
};
void bfs(int xx, int yy) //广搜连通块
{
node q[10010];
int head = 1;
int tail = 1;
q[tail].x = xx;
q[tail].y = yy;
tail++;
vis[xx][yy] = 10;
while(head<tail){
for(int i = 0; i < 4; i++){
int tx = q[head].x+next[i][0];
int ty = q[head].y+next[i][1];
if(tx<1||tx>n||ty<1||ty>n) continue;
if(s[tx][ty]==0&&vis[tx][ty]==0){
vis[tx][ty] = 10;
q[tail].x = tx;
q[tail].y = ty;
tail++;
}
}
head++;
}
}
int jud()
{
int flag = 1;
//判断是否存在边界点（存在边界点即没有被1包围）
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(vis[i][j]==10){
for(int k = 0; k < 4; k++){
int X = i+next[k][0];
int Y = j+next[k][1];
if(X<1||X>n||Y<1||Y>n) flag = 0;
}
}
}
if(flag==0) break;
}
if(flag==1){ //将封闭0改为2
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(vis[i][j]==10){
s[i][j] = 2;
}
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(vis[i][j]==10) vis[i][j] = 5;
}
}
}
int main()
{
cin >> n; //读入地图大小
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) cin >> s[i][j]; //读入地图
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(s[i][j]==0&&vis[i][j]==0){ //判断是否已经为连通块
bfs(i,j);//广搜连通块
jud();//判断是否被1封闭
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(j!=1) cout << " ";
cout << s[i][j];
}
cout << endl;
}
return 0;
}
https://blog.csdn.net/qq_45472594/article/details/106061310
扫描每一行，遇到第一个1后进入圈内，把遇到的0都赋值为2，遇到第二个1后出圈，遇到0不再赋值为2。需要考虑边界特殊情况。