admin 管理员组文章数量: 893696
P1162 填图颜色 洛谷(BFS的简单应用)
题目描述
由数字 0 0 0 组成的方阵中,有一任意形状闭合圈,闭合圈由数字 1 1 1 构成,围圈时只走上下左右 4 4 4 个方向。现要求把闭合圈内的所有空间都填写成 2 2 2。例如: 6 × 6 6\times 6 6×6 的方阵( n = 6 n=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(1 \le n \le 30) n(1≤n≤30)。
接下来 n n n 行,由 0 0 0 和 1 1 1 组成的 n × n n \times n n×n 的方阵。
方阵内只有一个闭合圈,圈内至少有一个 0 0 0。
//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)
输出格式
已经填好数字 2 2 2 的完整方阵。
样例 #1
样例输入 #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
提示
对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 30 1 \le n \le 30 1≤n≤30。
讲解
这道题其实用BFS挺简单的,就是注意索引从1开始,相当于在输入矩阵的最外层套一层0,然后从外层搜索,就ok了。这里有个小技巧就是把外围的0变成2,然后最后直接输出2-a[i][j]
就行了,这样外层的0还是0,1还是1,内层的0就是2了。
源代码
#include <bits/stdc++.h>using namespace std;const int N = 40;typedef pair<int, int> PII;int n;
int a[N][N];
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};void search(int x, int y)
{queue<PII> q;q.push({x, y});while(q.size()){auto t = q.front();q.pop();int x1 = t.first, y1 = t.second;// cout <<x1 <<' ' << y1 <<endl;a[x1][y1] = 2;for (int i = 0; i < 4; i ++ ){int xx = x1 + dx[i], yy = y1 + dy[i];if (xx >= 0 and xx <= n + 1 and yy >= 0 and yy <= n + 1 and a[xx][yy] == 0) q.push({xx, yy});}}
}int main()
{cin >> n;for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= n; j ++ ){cin >> a[i][j];}}search(0, 0);// cout <<endl;for (int i = 1; i <= n; i ++){for (int j = 1; j <= n; j ++ ){cout << 2 - a[i][j] << " \n"[j == n];}}}
本文标签: P1162 填图颜色 洛谷(BFS的简单应用)
版权声明:本文标题:P1162 填图颜色 洛谷(BFS的简单应用) 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1687604021h120120.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论