3 条题解

  • 1
    @ 2025-8-20 15:24:35
    #include<iomanip>
    #include<cmath>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    const int N=1e2+8;
    const int INF=0x3f3f3f3f;
    using namespace std;
    int m,n,ans;
    char a[N][N];
    int sx,sy;
    int dx[]={0,0,1,-1}; 
    int dy[]={1,-1,0,0}; 
    bool check(int x,int y)
    {
    	if(x>=0&&x<n&&y>=0&&y<m&&a[x][y]!='0')
    		return 1;
    	return 0;
    }
    void dfs(int x,int y) 
    {
    	a[x][y]='0';
    	for(int i=0;i<=3;i++)
    	{
    		int xx=x+dx[i];
    		int yy=y+dy[i];
    		if(check(xx,yy))
    			dfs(xx,yy);
    	}
    }
    int main()
    {
    	cin>>n>>m;
    	for(int i=0;i<n;i++)
    		cin>>a[i];
    	for(int i=0;i<n;i++)
    		for(int j=0;j<m;j++)
    		{
    			if(a[i][j]!='0')
    			{
    				ans++;
    				dfs(i,j);
    			}
    		}
    		cout<<ans;
    	return 0;
    }
    
    
    • 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
        @ 2023-8-25 17:05:21
        #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
        难度
        4
        标签
        递交数
        179
        已通过
        77
        上传者