苏州园区一站式服务中心,湛江做网站电话,课程商城网站模板,汉中市建设工程信息申报系统题目描述 由数字00组成的方阵中#xff0c;有一任意形状闭合圈#xff0c;闭合圈由数字11构成#xff0c;围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如#xff1a;6 \times 666的方阵#xff08;n6n6#xff09;#xff0c;涂色前和涂色后的… 题目描述 由数字00组成的方阵中有一任意形状闭合圈闭合圈由数字11构成围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如6 \times 66×6的方阵n6n6涂色前和涂色后的方阵如下 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 \le n \le 30)n(1≤n≤30) 接下来nn行由00和11组成的n \times nn×n的方阵。 方阵内只有一个闭合圈圈内至少有一个00。 //感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式) 输出格式 已经填好数字22的完整方阵。 输入输出样例 输入 #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说明/提示 1 \le n \le 301≤n≤30 题解 这道题有一个简单的算法就是输入时将所有为0的数据都填写为2然后从4个边向内部进行BFS如果搜索到2就将其改为0并继续搜索如果搜索到1或0就停止搜索。 1 #include iostream2 #include stdio.h3 #include math.h4 #include algorithm5 #include string.h6 7 using namespace std;8 9 const int MAXN 105;10 int n, map[MAXN][MAXN], vis[MAXN][MAXN];11 int pos[4][2] {0, 1, 0, -1, 1, 0, -1, 0};12 13 struct Node14 {15 int x, y;16 };17 18 Node q[MAXN];19 int front, rear;20 int a, b;21 22 void bfs()23 {24 Node now;25 now.x a;26 now.y b;27 if(map[a][b] ! 2)28 {29 return;30 }31 front rear 0;32 q[rear] now;33 rear; 34 while(front rear)35 {36 now q[front]; 37 if(map[now.x][now.y] 2)38 {39 map[now.x][now.y] 0;40 }41 if(now.x 7)42 {43 now.x 7;44 }45 for(int i 0; i 4; i) 46 {47 int nx now.x pos[i][0]; 48 int ny now.y pos[i][1]; 49 if(nx n nx 0 ny n ny 0 50 vis[nx][ny] false 51 map[nx][ny] 2) 52 {53 map[nx][ny] 0;54 vis[nx][ny] true;55 q[rear].x nx;56 q[rear].y ny;57 rear;58 }59 } 60 }61 }62 63 64 int main()65 {66 cin n;67 for(int i 1; i n; i)68 {69 for(int j 1; j n; j)70 {71 cin map[i][j];72 if(map[i][j] 0)73 {74 map[i][j] 2;75 }76 }77 }78 for(int i 1; i n; i)79 {80 a 1;81 b i;82 bfs();83 }84 for(int i 1; i n; i)85 {86 a n;87 b i;88 bfs();89 }90 for(int i 1; i n; i)91 {92 a i;93 b 1;94 bfs();95 }96 for(int i 1; i n; i)97 {98 a i;99 b n;
100 bfs();
101 }
102 for(int i 1; i n; i)
103 {
104 for(int j 1; j n; j)
105 {
106 cout map[i][j] ;
107 }
108 cout endl;
109 }
110 return 0;
111 } 这个BFS并不难写不过当时犯了一个小错误导致2/3/4个样例都是WA特别是第2个样例在本机输出的结果和标准答案一致但是提交后总是说一个位置应该为0输出了2。查了很久最后发现是把pos[4][2]写成了pos[2][4]。数组定义错了导致遍历时移动的位置错误了而且本机的对应内存的数据和测试机不同所以在本机上是过了但是测试机没有过。 转载于:https://www.cnblogs.com/zealsoft/p/11404420.html
