- C++
信奥下午班作业提交界面
- 2024-2-19 18:04:57 @
20240219寒假集训作业(可选) 1、把上课梳理过的连通图和围成面积两道题,重新独立进行编程提交(不参考示例代码)。 2、把上课梳理过的连通图和围成面积两道题实例代码加上注释理解。
2 条评论
-
lihonglang0825 LV 2 @ 2024-2-20 9:40:20
自己写: “围成面积”代码:
#include<bits/stdc++.h> using namespace std; int a[20][20], b[400][2], ans = 0, sum = 0, n = 10, m = 10; void bfs(int x, int y) { int dd = 1, tt = 2; b[1][0] = x; b[1][1] = y; a[x][y] = 1; ans++; while (dd < tt) { x = b[dd][0]; y = b[dd][1]; if (a[x - 1][y] == 0) { a[x - 1][y] = 1; b[tt][0] = x - 1; b[tt++][1] = y; ans++; } if (a[x + 1][y] == 0) { a[x + 1][y] = 1; b[tt][0] = x + 1; b[tt++][1] = y; ans++; } if (a[x][y - 1] == 0) { a[x][y - 1] = 1; b[tt][0] = x; b[tt++][1] = y - 1; ans++; } if (a[x][y + 1] == 0) { a[x][y + 1] = 1; b[tt][0] = x; b[tt++][1] = y + 1; ans++; } dd++; } } int main() { for (int i = 2; i <= n + 1; i++) { for (int j = 2; j <= m + 1; j++) { cin >> a[i][j]; if (a[i][j] == 1) { sum++; } } } for (int i = 0; i <= n + 3; i++) { for (int j = 0; j <= m + 3; j++) { if ((i == 0 && j <= 13) || (i == 13 && j <= 13) || (j == 0 && i <= 13) || (j == 13 && i <= 13)) { a[i][j] = 1; } } } bfs(1, 1); cout << 144 - sum - ans; return 0; }
“连通块”代码:
#include<bits/stdc++.h> using namespace std; int a[1000][1000], b[1000 * 1000][2], ans; void bfs(int x, int y) { int dd = 1, tt = 2; b[1][0] = x; b[1][1] = y; while (dd < tt) { x = b[dd][0]; y = b[dd][1]; if (a[x - 1][y] == 1) { b[tt][0] = x - 1; b[tt++][1] = y; } if (a[x + 1][y] == 1) { b[tt][0] = x + 1; b[tt++][1] = y; } if (a[x][y - 1] == 1) { b[tt][0] = x; b[tt++][1] = y - 1; } if (a[x][y + 1] == 1) { b[tt][0] = x; b[tt++][1] = y + 1; } a[x][y] = 0; dd++; } } int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i][j] == 1) { ans++; bfs(i, j); } } } cout << ans; return 0; }
-
2024-2-19 20:42:19@
连通块注释:
#include<bits/stdc++.h>//头文件 using namespace std;//命名空间 const int N=1e4+10;//数组大小 int n,m,a[N][N],ans=0,q[N*N][2];//行数、列数、储存图形的二维数组、答案、储存行列数的队列 void bfs(int x,int y){//把连通的块变成'0' int dd=1,tt=2;//判断是否还有连通的块的变量 q[1][0]=x;//入队 q[1][1]=y;//入队 while(dd<tt){//判断是否还有连通的块 x = q[dd][0];//改变搜索范围 y = q[dd][1];//改变搜索范围 if(a[x-1][y]==1){q[tt][0]=x-1;q[tt++][1]=y;}//上方向是否为1,并且清空、入队 if(a[x+1][y]==1){q[tt][0]=x+1;q[tt++][1]=y;}//下方向是否为1,并且清空、入队 if(a[x][y-1]==1){q[tt][0]=x;q[tt++][1]=y-1;}//左方向是否为1,并且清空、入队 if(a[x][y+1]==1){q[tt][0]=x;q[tt++][1]=y+1;}//右方向是否为1,并且清空、入队 a[x][y]=0;//连通的地方清空 dd++;//寻找的次数加1 } } int main(){//主函数 cin>>n>>m;//输入行列数 for(int i=1;i<=n;i++)//行 for(int j=1;j<=m;j++)cin>>a[i][j];//输入图形 for(int i=1;i<=n;i++){//行 for(int j=1;j<=m;j++){//查找元素 if(a[i][j]==1){//判断是否为另一个连通块 ans++;//连通块的数量加1 bfs(i,j);//把连起来的块变成0 } } } cout<<ans;//输出答案 return 0;//结束程序 }
围成面积注释:
#include<bits/stdc++.h>//头文件 using namespace std;//命名空间 int n=10,m=10,a[20][20],ans=0,q[400][2],sum=0;//图案行数和列数,储存图案的数组,是'0'部分的数量,储存行列数的队列,是'1'部分的数量 void bfs(int x,int y){//有多少联通的'0' int dd=1,tt=2;//判断是否还有连通块的变量 q[1][0]=x;//行数入队 q[1][1]=y;//列数入队 a[x][y]=1;//把判断的块变成'1' ans++;//连通的数量加1 while(dd<tt){//判断是否还有连通的块 x = q[dd][0];//改变搜索范围 y = q[dd][1];//改变搜索范围 if(a[x-1][y]==0){a[x-1][y]=1;q[tt][0]=x-1;q[tt++][1]=y;ans++;}//上方向是否为1,并且变成1、入队,连通数量加1 if(a[x+1][y]==0){a[x+1][y]=1;q[tt][0]=x+1;q[tt++][1]=y;ans++;}//下方向是否为1,并且变成1、入队,连通数量加1 if(a[x][y-1]==0){a[x][y-1]=1;q[tt][0]=x;q[tt++][1]=y-1;ans++;}//左方向是否为1,并且变成1、入队,连通数量加1 if(a[x][y+1]==0){a[x][y+1]=1;q[tt][0]=x;q[tt++][1]=y+1;ans++;}//右方向是否为1,并且变成1、入队,连通数量加1 dd++;//寻找次数加1 } } int main(){//主函数 for(int i=2;i<=n+1;i++)// for(int j=2;j<=m+1;j++){//列 cin>>a[i][j];//输入图形 if(a[i][j]==1)sum++;//'1'的数量 } for(int i=0;i<=n+3;i++)//图案所有的行 for(int j=0;j<=m+3;j++){//图案有的列 if((i==0&&j<=13)||(i==13&&j<=13)||(j==0&&i<=13)||(j==13&&i<=13)){//图案的左右边和上下边 a[i][j]=1;//图案边缘变成'1' } } bfs(1,1);//所有'0'的数量 cout<<144-ans-sum;//所有的-多余的-周围的=围起来的 return 0;//程序结束 }
- 1