写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：P1162 填涂颜色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述：
输入格式：
每组测试数据第一行一个整数 n (1 ≤ n ≤ 30)。
接下来 n 行，由 0 和 1 组成的 n × n 的方阵。
方阵内只有一个闭合圈，圈内至少有一个 0。
输出格式：
已经填好数字 22 的完整方阵。
输入样例：
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
解题思路：
这道题就是让我们将被1围起来的位置全部涂上色，
大致的思路就是：
1. 先将在外面的0用状态数组存为true
2. 而剩下位置的0，也就是需要涂色的0就都是false,
3. 完成区分后，我们就直接将需要涂色的0全部置为2即可，
另外需要注意一些特殊情况，
如果我们开始搜索的位置是1，
那就会出问题，
我们可以将这个地图外围加一圈0:
这样搜索的时候就能保证，
将所有外围的0的位置全部改变状态，
下面是代码实现：
代码：
//包好头文件 #include #include #include #include using namespace std; const int N = 35; int n; typedef pair PII; bool st[N][N]; int g[N][N]; PII q[N * N]; //存偏移量 int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; int head = 0; int tail = -1; void bfs(int x, int y) { q[++tail] = {x, y}; st[x][y] = true; while(head <= tail) { auto t = q[head++]; for(int i = 0; i < 4; i++) { int a = t.first + dx[i]; int b = t.second + dy[i]; if(a < 0 || a > n + 1 || b < 0 || b > n + 1) continue; if(g[a][b] == 1) continue; if(st[a][b] == true) continue; //将在外面的位置置为true st[a][b] = true; q[++tail] = {a, b}; } } } int main() { scanf("%d", &n); //读入地图 for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { scanf("%d", &g[i][j]); } } bfs(1, 1); //将1包围的位置置为2 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++) { printf("%d ", g[i][j]); } puts(""); } return 0; }
AC ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
