• C++
  • 信奥下午班作业提交界面

  • @ 2024-2-19 18:04:57

20240219寒假集训作业(可选) 1、把上课梳理过的连通图和围成面积两道题,重新独立进行编程提交(不参考示例代码)。 2、把上课梳理过的连通图和围成面积两道题实例代码加上注释理解。

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