今天遇到了一种新题型，关于染色。
那么这种题型有什么特点呢？
•特点：
对于这种题，一般是给你一个“地图”，其中有多个障碍，对障碍内部的元素进行处理或统计；
比如：
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“染成”2”（这就是本篇博文例2的样例），所以这类问题被称作染色问题；
•基本思路：
接下来讲讲这类问题的通解；
步骤（一）：将原地图化为数字地图（如果原来就是数字地图，直接略过），存到map数组里（如果担心重名，可以存到atl数组里，atlas也是地图的意思）
步骤（二）：进入广度优先搜索部分（其实就是模拟），从（0 , 0）开始搜索，如果出界或碰到障碍，就回溯；
步骤（三）：如果没有回溯，就把该元素定义为2，上下左右继续搜索；
步骤（四）：按题目所求输出；
光说不练假把式，请大家打开洛谷，分别找到P1162填图染色和P1506拯救oibh总部
•例题（1）：
对于这道题，我们可以套用基本思路，下面是略带注释的代码：
1 #include<cstdio>
2 #include<iostream>
3 #define maxn 550
4 using namespace std;
5 int dx[5]={0,0,1,0,-1},dy[5]={0,1,0,-1,0};//将向上、向下、向左、向右和不动的横纵坐标的变化值分别存到dx和dy数组里
6 int atl[maxn][maxn];
7 char catl;
8 int xx,yy;
9 int ans;
10 void bfs(int,int);
11 int main()
12 {
13 cin>>xx>>yy;
14 for(int i=1;i<=xx;++i)
15 {
16 for(int j=1;j<=yy;++j)
17 {
18 cin>>catl;//将题目中的地图用字符串读入
19 if(catl=='0') atl[i][j]=0;
20 else atl[i][j]=1;
21 }
22 }
23 bfs(0,0);//发大水啦！！！
24 for(int i=1;i<=xx;++i)
25 for(int j=1;j<=yy;++j)
26 if(!atl[i][j]) ans++;//如果没有被淹，那么答案加1
27 cout<<ans<<endl;
28 return 0;
29 }
30
31 void bfs(int a,int b)
32 {
33 if(a<0 || b<0 || a>xx+1 || b>yy+1 || atl[a][b]) {return;} //如果搜索到边界或者障碍，就回溯
34 atl[a][b]=2;//否则就把该元素变为2
35 for(int i=1;i<=4;++i)
36 {
37 bfs(a+dx[i],b+dy[i]);//这个过程表示向上下左右继续搜索
38 }
39 }
•例题（2）：
这道题的思路和上一道题雷同，这里就不再赘述了，大家看看代码就好：
1 #include<cstdio>
2 #include<iostream>
3 #define maxn 550
4 using namespace std;
5 int dx[5]={0,0,1,0,-1},dy[5]={0,1,0,-1,0};
6 int atl[maxn][maxn];
7 int n;
8 int ans;
9 void bfs(int,int);
10 int main()
11 {
12 cin>>n;
13 for(int i=1;i<=n;++i)
14 {
15 for(int j=1;j<=n;++j)
16 {
17 cin>>atl[i][j];
18 }
19 }
20 bfs(0,0);
21 for(int i=1;i<=n;++i)
22 {
23 if(i>=2) cout<<endl;
24 for(int j=1;j<=n;++j)
25 {
26 if(atl[i][j]==2) cout<<0<<" ";
27 if(atl[i][j]==1) cout<<1<<" ";
28 if(atl[i][j]==0) cout<<2<<" ";//唯一与上一题不一样的就是输出
29 }
30 }
31 return 0;
32 }
33
34 void bfs(int a,int b)
35 {
36 if(a<0 || b<0 || a>n+1 || b>n+1 || atl[a][b]) {return;}
37 atl[a][b]=2;
38 for(int i=1;i<=4;++i)
39 {
40 bfs(a+dx[i],b+dy[i]);
41 }
42 }
2019-04-20 16:29:46