2 条题解

  • 1
    @ 2021-10-18 21:27:06
    #include <stdio.h>
    #include <iostream>
    #include <queue> 
    using namespace std;
    
    int n , m;
    char a[200][200];
    struct node 
    {
    	int x,y;	
    };
    int dx[] = {1,0,-1,0};
    int dy[] = {0,1,0,-1};
    void bfs(int x, int y)
    {
    	queue<node> p;
    	p.push( (node){x,y} );
    	a[x][y] = '0';
    	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];
    			if(x >= 0 && x < n && y >= 0 && y < m && a[x][y] != '0')
    			{
    				p.push((node){x,y});
    				a[x][y] = '0';
    			}
    		}
    		 
    	}
    }
    int main()
    {
    	cin >>n >> m;
    	for(int i = 0 ;i < n ; i++)
    		cin >> a[i];
    	
    	int ans = 0;
    	for(int i = 0 ; i < n ; i++)
    	{
    		for(int j = 0 ; j < m ; j++)
    		{
    			if(a[i][j] != '0')
    			{
    				bfs(i,j);
    				ans++;
    			}
    		}
    	}
    	cout << ans << endl; 
    }
    
    • 0
      #include <iostream>
      #include <cstring> 
      #include <queue>
      using namespace std;
      struct point{
      	int x,y;
      }; 
      point s,t;
      int n,m,cnt;
      char a[1010][1010];
      bool vis[1010][1010];
      int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
      void bfs(point s){
      	queue<point>q;
      	q.push(s);
      	vis[s.x][s.y]=1;
      	while(!q.empty()){
      		point cur=q.front();
      		q.pop();
      		for(int i=0;i<4;i++){
      			point nxt;
      			nxt.x=cur.x+dx[i];
      			nxt.y=cur.y+dy[i];
      			if(nxt.x<1||nxt.x>n||nxt.y<1||nxt.y>m)continue;
      			if(a[nxt.x][nxt.y]!='0'&&!vis[nxt.x][nxt.y]){
      				q.push(nxt);
      				vis[nxt.x][nxt.y]=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]!='0'&&!vis[i][j]){
      				bfs({i,j});
      				cnt++;
      			}
      		}
      	}
      	cout<<cnt<<endl;
      	return 0;
      }
      
      • 1

      信息

      ID
      1309
      时间
      1000ms
      内存
      256MiB
      难度
      3
      标签
      递交数
      79
      已通过
      43
      上传者