题解 P1162 【填涂颜色】
标准搜索题
题目描述： 由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6×6的方阵（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(1≤n≤30)
接下来n行，由0和1组成的n×n的方阵。
方阵内只有一个闭合圈，圈内至少有一个0。
首先看数据：n<=30 数据很小，搜索不会TLE，不用优化。
再看描述：方阵内只有一个闭合圈，圈内至少有一个0。
也就是说，除1与1包围的0以外，其他0都在外围
不用多说，搜索染色法，可以轻松拓展在一起的0。但这时，问题就来了：怎么搜外围？ 众所周知，外围是有1的（如题目描述样例）
case1 ：枚举外围：开循环枚举
蒟蒻专用写法 代码如下，枚举外围每个点，不难理解。
for(int i=1;i<=n;i++)if(f[i][1]==0)bfs(i,1);//第一列 for(int i=1;i<=n;i++)if(f[i][n]==0)bfs(i,n);//第n列 for(int i=1;i<=n;i++)if(f[1][i]==0)bfs(1,i);//第一行 for(int i=1;i<=n;i++)if(f[n][i]==0)bfs(n,i);//第n行
虽然可以，但是 有没有觉得太麻烦了点？
case2:围上一圈0
先拿样例来说：如果在外围围上一圈0，会怎样？
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0
0 0 1 1 0 0 1 0
0 1 1 0 0 0 1 0
0 1 0 0 0 0 1 0
0 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
如果这样做，那么可以发现……由外圈开始，一定能搜到所有0！ 于是，我们只需要短短的一行来搜索。
bfs(0,0);
上代码~
广搜代码
#include<bits/stdc++.h>//万能头，懒人专用
using namespace std;
int f[32][32];
int dx[4]= {0,1,0,-1},dy[4]= {1,0,-1,0};//存储方向
int n;
queue<int>q;//使用stl队列
void bfs(int x,int y) {//广搜
int x1,x2,y1,y2;//这里别学我开y1变量，有时候会被判断为一个函数y1，然后gg
q.push(x);//存储x(下同)
q.push(y);//存储y(下同)
f[x][y]=2;//染色(下同)
while(!q.empty()) {//队列不为空
x1=q.front();
q.pop();
y1=q.front();
q.pop();//获得队头数据
for(int i=0; i<4; i++) {//向四个方向搜索
x2=x1+dx[i];
y2=y1+dy[i];//用变量，下文判断更方便
if(x2>=0&&x2<=n+1&&y2>=0&&y2<=n+1&&f[x2][y2]==0) {
q.push(x2);
q.push(y2);
f[x2][y2]=2;
}//满足条件，入队
}
}
return;
}
int main() {
cin>>n;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
cin>>f[i][j];
}
bfs(0,0);//从(0,0)开始，一定能搜到外圈省去多余枚举外圈代码
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++)
cout<<(f[i][j]==0?2:(f[i][j]==1?1:0))<<' ';//装B专用写法，意为如果为0输出2，否则如果为1输出1，否则输出0
cout<<endl;//别忘记输出回车
}
return 0;//好习惯
}深搜代码
void dfs(int x,int y) {
f[x][y]=2;//染色
for (int i=0; i<4; i++)
if(x>=0&&x<=n+1&&y>=0&&y<=n+1&&f[x][y]==0)
dfs(x+dx[i],y+dy[i]);
}至于打哪种搜索，可以选择自己不熟练的进行练习（就像我不熟悉广搜，就打了个广搜代码）