5 条题解

  • 1
    @ 2022-1-25 15:19:50
    /*********************************
    备注:
    *********************************/
    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <queue>
    #include <math.h>
    #include <vector>
    #include <algorithm>
    #include <iomanip>
    #include <stack>
    using namespace std;
    #define LL long long
    const int N =1e5+10;
    const int INF =0x3f3f3f3f;
    int mp[100][100],a[100][100],n,m;
    int dx[]{0,-1,0,1};
    int dy[]{-1,0,1,0};
    struct node{
    	int x,y;
    };
    int bfs(int x,int y){
    	queue<node> p;
    	p.push((node){x,y});
    	a[x][y]=1;
    	int sum=1;
    	while(!p.empty()){
    		node t=p.front(); 
    		p.pop();
    		for(int i=0;i<4;i++){
    			x=t.x+dx[i];
    			y=t.y+dy[i];
    			int s=mp[t.x][t.y]&(1<<i);
    			if(s==0&&!a[x][y]){
    				a[x][y]=++sum;
    				p.push((node){x,y});
    			} 
    		} 
    	}
    	return sum;
    }
    int main(){
    	cin>>n>>m;
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++){
    			cin>>mp[i][j]; 
    		}
    	}
    	int num=0,maxx=0;
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++){
    			if(a[i][j]==0){
    				num++;
    				maxx=max(maxx,bfs(i,j));
    			}
    		}
    	}
    	cout<<num<<endl;
    	cout<<maxx<<endl;
    	return 0;
    }
    
    • 0
      @ 2024-2-3 10:13:01
      #include<iostream>
      #include<cstdio>
      #include<queue>
      #include<cmath>
      #include<cstring>
      #include<bits/stdc++.h>
      using namespace std;
      int dx[]={0,-1,0,1};
      int dy[]={-1,0,1,0};
      int ans=0;
      int n,m,x,y,b,maxx;
      int a[100][100],v[100][100];
      struct node{
      	int x,y;
      };
      queue<node>q;
      
      void bfs(int x,int y){
          q.push((node){x,y});
          int cnt=1;
          v[x][y]=1;
          while(!q.empty()){
          	node top=q.front();
          	q.pop();
          	for(int i=0;i<=3;i++){
          		int xx=top.x+dx[i];
          		int yy=top.y+dy[i];
          		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&v[xx][yy]==0&&(a[top.x][top.y]&(1<<i))==0){
          			cnt++;
          			v[xx][yy]=1;
          			q.push((node){xx,yy});
      			}
      		}
      	}
      	maxx=max(maxx,cnt);
      }
      
      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(v[i][j]==0){
          			ans++;
          			bfs(i,j);
      			}
      		}
      	}
      	cout<<ans<<endl<<maxx;
      }
      
      • 0

        #include<iostream> #include<bits/stdc++.h> using namespace std; const int N=1145; int a[N][N]; bool v[N][N]; int m,n,maxx,ans; int dx[]={0,-1,0,1}; int dy[]={-1,0,1,0}; struct node{ int x,y; }; queue<node>q; void bfs(int x,int y){ q.push((node){x,y}); int cnt=1; v[x][y]=1; while(!q.empty()){ node top=q.front(); q.pop(); for(int i=0;i<=3;i++){ int xx=top.x+dx[i]; int yy=top.y+dy[i]; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&v[xx][yy]==0&&(a[top.x][top.y]&(1<<i))==0){ cnt++; v[xx][yy]=1; q.push((node){xx,yy}); } } } maxx=max(maxx,cnt); } 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(v[i][j]==0) { ans++; bfs(i,j);

        }
        

        }

        cout<<ans<<endl<<maxx; return 0; }

        • 0
          @ 2024-1-31 17:02:28
          #include <stdio.h>
          #include <queue>
          #include <stack>
          #include <algorithm>
          #include <iostream>
          #include <math.h>
          #include <string.h>
          #include <vector>
          #define LL long long
          const int INF = 0x3f3f3f3f;
          const int N = 50+10;
          using namespace std;
          
          int n , m , a[N][N] , ans , maxx; 
          bool v[N][N];
          int dx[] = {0, -1 , 0 , 1};//西北东南 
          int dy[] = {-1, 0 , 1 , 0};
          
          struct node
          {
          	int x , y;	
          };
          
          queue<node> q;
          
          void bfs(int x , int y)
          {
          	q.push((node){x , y});
          	int cnt = 1;
          	v[x][y] = 1;
          	while(!q.empty())
          	{
          		node top = q.front();
          		q.pop();
          		for(int i = 0 ; i <= 3; i++)
          		{
          			int xx = top.x + dx[i];
          			int yy = top.y + dy[i];
          			//(a[top.x][top.y] & (1 << i)) == 0 判断是否有墙 
          			if( xx >= 1 && xx <= n && yy >= 1 && yy <= m && v[xx][yy] == 0 && (a[top.x][top.y] & (1 << i)) == 0 )
          			{
          				cnt++;	
          				v[xx][yy] = 1;
          				q.push((node){xx , yy});
          			}
          		}
          	}
          	maxx = max(maxx , cnt);
          }
          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(v[i][j] == 0)//当前点没有访问过 
          			{
          				ans++;
          				bfs(i , j);
          			}
          		}
          		
          	cout << ans << endl << maxx;
          	return 0;
          }
          
          • 0
            @ 2022-1-17 21:50:45
            #include <iostream>
            #include <stdio.h>
            #include <string.h>
            #include <queue>
            #include <math.h>
            #include <vector>
            #include <algorithm>
            #include <iomanip>
            #include <stack>
            
            using namespace std;
            
            #define LL long long
            const int N =1e5+10;
            const int INF =0x3f3f3f3f;
            int mp[100][100],a[100][100],n,m;
            int dx[]{0,-1,0,1};
            int dy[]{-1,0,1,0};
            struct node{
            	int x,y;
            };
            int bfs(int x,int y){
            	queue<node> p;
            	p.push((node){x,y});
            	a[x][y]=1;
            	int sum=1;
            	while(!p.empty()){
            		node t=p.front(); 
            		p.pop();
            		for(int i=0;i<4;i++){
            			x=t.x+dx[i];
            			y=t.y+dy[i];
            			int s=mp[t.x][t.y]&(1<<i);
            			if(s==0&&!a[x][y]){
            				a[x][y]=++sum;
            				p.push((node){x,y});
            			} 
            		} 
            	}
            	return sum;
            }
            int main(){
            	cin>>n>>m;
            	for(int i=0;i<n;i++){
            		for(int j=0;j<m;j++){
            			cin>>mp[i][j]; 
            		}
            	}
            	int num=0,maxx=0;
            	for(int i=0;i<n;i++){
            		for(int j=0;j<m;j++){
            			if(a[i][j]==0){
            				num++;
            				maxx=max(maxx,bfs(i,j));
            			}
            		}
            	}
            	cout<<num<<endl;
            	cout<<maxx<<endl;
            	return 0;
            }
            
            • 1

            信息

            ID
            1344
            时间
            1000ms
            内存
            256MiB
            难度
            5
            标签
            递交数
            106
            已通过
            44
            上传者