做网站要审批吗,关键词分析软件,网站信息备案管理系统,设计与制作题目描述
由数字 0 0 0 组成的方阵中#xff0c;有一任意形状闭合圈#xff0c;闭合圈由数字 1 1 1 构成#xff0c;围圈时只走上下左右 4 4 4 个方向。现要求把闭合圈内的所有空间都填写成 2 2 2。例如#xff1a; 6 6 6\times 6 66 的方阵#xff08; n 6 n6 n6有一任意形状闭合圈闭合圈由数字 1 1 1 构成围圈时只走上下左右 4 4 4 个方向。现要求把闭合圈内的所有空间都填写成 2 2 2。例如 6 × 6 6\times 6 6×6 的方阵 n 6 n6 n6涂色前和涂色后的方阵如下
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 10 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。
输出格式
已经填好数字 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。
一、错误分析
题意就是把被1包围的0改成2。 那么只需要找到包围起来的第一个0的坐标就可以把所有被包围的0改成2。 第一个0的坐标是第一个1的右下角 那么就有了下面错误的代码WA了一个测试点
//错误代码
#include iostream
#include queue
using namespace std;
int n;
int dir[][2] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int a[33][33];
struct node
{int x, y;
};
int main()
{cin n;int sx 0, sy 0;for (int i 1; i n; i)for (int j 1; j n; j){cin a[i][j];if (a[i][j] 1 sx 0){sx i, sy j;}}sx;sy;// bfs广度优先queuenode q;q.push({sx, sy});while (!q.empty()){node p q.front();q.pop();for (int i 0; i 4; i){int nx p.x dir[i][0], ny p.y dir[i][1];if (!(nxn||nyn||nx1||ny1)a[nx][ny] 0){q.push({nx, ny});a[nx][ny] 2;}}}for (int i 1; i n; i){for (int j 1; j n; j){cout a[i][j] ;}cout endl;}
}那么当墙有厚度的时候这种找0的方法是错误的。 比如下面这组测试数据。
6
1 1 1 1 1 1
1 0 0 0 0 0
1 1 1 1 1 1
1 1 0 0 1 1
1 1 0 0 1 1
1 1 1 1 1 1 二、正确分析
先将二维数组初始化为2将有1的地方改为1那么被1包围之外的2就是连续的了只需要使用dfs或bfs就能够把所有包围之外的2改为0。 二维数组需要往外扩展一圈这样就能保证包围之外的2是连续的。 如[1,n]的区间拓展为[0,n1].
方法1.DFS
#include iostream
#include queue
using namespace std;
int n;
int dir[][2] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int a[35][35];
struct node
{int x, y;
};
void dfs(int x,int y)
{if(xn1||yn1||x0||y0) return ;if(a[x][y] 1||a[x][y]0) return;a[x][y]0;for (int i 0; i 4; i){dfs(x dir[i][0],y dir[i][1]);}
}
int main()
{for(int i0;i33;i)for(int j0;j33;j){a[i][j]2;}cin n;for (int i 1; i n; i)for (int j 1; j n; j){int t;cin t;if(t1) a[i][j]1;}dfs(0,0);for (int i 1; i n; i){for (int j 1; j n; j){cout a[i][j] ;}cout endl;}
}方法2.BFS
#include iostream
#include queue
using namespace std;
int n;
int dir[][2] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int a[35][35];
struct node
{int x, y;
};
int main()
{for(int i0;i33;i)for(int j0;j33;j){a[i][j]2;}cin n;for (int i 1; i n; i)for (int j 1; j n; j){int t;cin t;if(t1) a[i][j]1;}queuenode q;q.push({0, 0});while (!q.empty()){node p q.front();q.pop();for (int i 0; i 4; i){int nx p.x dir[i][0], ny p.y dir[i][1];if (!(nxn1||nyn1||nx0||ny0)a[nx][ny] 2){q.push({nx, ny});a[nx][ny] 0;}}}for (int i 1; i n; i){for (int j 1; j n; j){cout a[i][j] ;}cout endl;}
}
