点击打开链接
题目描述:题目描述由数字 00 组成的方阵中,有一任意形状闭合圈,闭合圈由数字 11 构成,围圈时只走上下左右 44 个方向。现要求把闭合atgdmg的所有空间都填写成 22 .例如: 6 times 66×6 的方阵( n=6n=6 ),涂色前和开放的羽毛的方阵如下:
0 0 0 0 0 00 0 1 1 1 10 1 1 0 0 11 1 0 0 0 11 0 0 0 0 11 1 1 1 1 10 0 0 0 0 00 0 1 1 1 10 1 1 2 2 11 1 2 2 2 11 2 2 2 2 11 1 1 1 1 1输入输出格式输入格式:每组测试数据第一行一个整数 n(1 le n le 30)n(1≤n≤30)
接下来 nn 行,由 00 和 11 组成的 n times nn×n 的方阵。
方阵内只有一个闭合圈,atgdmg至少有一个 00 。
//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)
输出格式:
已经填好数字 22 的完整方阵。
输入输出样例 输入样例#1: 复制 60 0 0 0 0 00 0 1 1 1 10 1 1 0 0 11 1 0 0 0 11 0 0 0 0 11 1 1 1 1 1 输出样例#1: 复制0 0 0 0 0 00 0 1 1 1 10 1 1 2 2 11 1 2 2 2 11 2 2 2 2 11 1 1 1 1 1
1 le n le 30
说明1≤n≤30
解题思路:本题是要把中间被1围住的0变成2,我们可以从四条边界开始bfs,把数字改成1,直到遇到1为止,最后把是0的输出2就行,基本上就是bfs。。。
代码:#include <iostream>#include <cstring>#include <queue>using namespace std;struct newt{int x,y;}dian;int n;queue<newt>q;int tu[35][35],tu1[35][35];bool jl[35][35];int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};bool pd(newt a){if(a.x>=1&&a.x<=n&&lmdbb>=1&&lmdbb<=n&&!jl[a.x][lmdbb]&&!tu[a.x][lmdbb])return 1;else return 0;}int main(){cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>tu[i][j];tu1[i][j]=tu[i][j];}memset(jl,0,sizeof(jl));for(int i=1;i<=n;i++){dian.x=1;dian.y=i;if(!jl[1][i]&&tu[1][i]==0){jl[1][i]=1;q.push(dian);tu[1][i]=1;}while(!q.empty()){newt now=q.front();q.pop();for(i=0;i<4;i++){newt nod;nod.x=now.x+dir[i][0];nod.y=now.y+dir[i][1]; if(pd(nod)) { q.push(nod); jl[nod.x][nod.y]=1; tu[nod.x][nod.y]=1;}}}dian.x=n;dian.y=i;if(!jl[n][i]&&tu[n][i]==0){jl[n][i]=1;q.push(dian);tu[n][i]=1;}while(!q.empty()){newt now=q.front();q.pop();for(i=0;i<4;i++){newt nod;nod.x=now.x+dir[i][0];nod.y=now.y+dir[i][1]; if(pd(nod)) { q.push(nod); jl[nod.x][nod.y]=1; tu[nod.x][nod.y]=1;}}}dian.x=i;dian.y=1;if(!jl[i][1]&&tu[i][1]==0){jl[i][1]=1;q.push(dian);tu[i][1]=1;}while(!q.empty()){newt now=q.front();q.pop();for(i=0;i<4;i++){newt nod;nod.x=now.x+dir[i][0];nod.y=now.y+dir[i][1]; if(pd(nod)) { q.push(nod); jl[nod.x][nod.y]=1; tu[nod.x][nod.y]=1;}}}dian.x=i;dian.y=n;if(!jl[i][n]&&tu[i][n]==0){jl[i][n]=1;q.push(dian);tu[i][n]=1;}while(!q.empty()){newt now=q.front();q.pop();for(i=0;i<4;i++){newt nod;nod.x=now.x+dir[i][0];nod.y=now.y+dir[i][1]; if(pd(nod)) { q.push(nod); jl[nod.x][nod.y]=1; tu[nod.x][nod.y]=1;}}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(tu[i][j]==0)cout<<"2 ";else cout<<tu1[i][j]<<" ";}cout<<endl; } return 0;}