1 solutions

  • 0
    @ 2022-4-20 21:04:32

    `

    #include<iostream>
    #include<queue>
    using namespace std;
    typedef pair<int,int> PAII;
    int n,m;
    const int N=5050;
    char ch[N][N];
    bool st[N][N];
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    void bfs(int x,int y)
    {
    	queue<PAII> q;
    	q.push({x,y});
    	st[x][y]=true;
    	while(q.size())
    	{
    		auto t=q.front();
    		q.pop();
    		int a=t.first,b=t.second;
    		for(int i=0;i<4;i++)
    		{
    			int xx=a+dx[i],yy=b+dy[i];
    			if(xx<0||yy<0||xx>=n||yy>=m) continue;
    			if(ch[xx][yy]!='0'&&!st[xx][yy])
    			{
    				q.push({xx,yy});
    				st[xx][yy]=true;
    			}
    		}
    	}
    }
    int main(){
    	cin>>n>>m;
    	for(int i=0;i<n;i++)
    		for(int j=0;j<m;j++)
    			cin>>ch[i][j];
    	int sum=0;
    	for(int i=0;i<n;i++)
    	{
    		for(int j=0;j<m;j++)
    		{
    			if(!st[i][j]&&ch[i][j]!='0')
    			{
    				sum++;
    				bfs(i,j);
    			}
    		}
    	}
    	cout<<sum;
    	return 0;
    }
    
    • 1

    Information

    ID
    1243
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    9
    Tags
    # Submissions
    10
    Accepted
    9
    Uploaded By