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;
    }
    
    • 0
      @ 2022-3-25 19:13:14
      #include <stdio.h>
      #include <math.h>
      #include <algorithm>
      #include <iostream>
      #include <string.h>
      #include <queue>
      #include <stack>
      #include <map>
      #include <set>
      #include <vector>
      using namespace std;
      int n,m,ans;
      int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0};
      char a[105][105];
      int vis[105][105];
      void dfs(int xx,int yy) {
          vis[xx][yy]=1;
          for(int i=0; i<4; i++) {
              int x=xx+dx[i],y=yy+dy[i];
              if(x>=0&&y>=0&&x<n&&y<m&&!vis[x][y]&&a[x][y]=='W') {
                  dfs(x,y);
              }
          }
      }
      int main() {
          scanf("%d%d",&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(!vis[i][j]&&a[i][j]=='W') {
                      ans++;
                      dfs(i,j);
                  }
              }
          }
          cout<<ans<<endl;
          return 0;
      }
      
      • 1

      Information

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