2 solutions

  • 0
    @ 2022-4-12 18:13:06
    #include<iostream>
    #include<queue>
    using namespace std;
    typedef pair<int,int> PAII;
    int n,m;
    const int N=1010;
    char ch[N][N];
    bool st[N][N];
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    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&&ch[xx][yy]=='W'&&!st[xx][yy])
    			{
    				q.push({xx,yy});
    				st[xx][yy]=true;
    			}
    		}
    	}
    }
    int main(){
    	int sum=0;
    	cin>>n>>m;
    	for(int i=0;i<n;i++)
    		for(int j=0;j<m;j++)
    			cin>>ch[i][j];
    	for(int i=0;i<n;i++)
    		for(int j=0;j<m;j++)
    		{
    			if(ch[i][j]=='W'&&!st[i][j])
    			{
    				sum++;
    				bfs(i,j);
    			}
    		}
    	cout<<sum;
    	return 0;
    }
    

    Information

    ID
    771
    Time
    1000ms
    Memory
    16MiB
    Difficulty
    5
    Tags
    # Submissions
    63
    Accepted
    26
    Uploaded By