2 条题解

  • 0
    @ 2023-6-17 10:08:53
    #include<bits/stdc++.h>
    using namespace std;
    char ch[110][110];
    int n,m,v[110][110],num;
    int dx[4]={1,0,-1,0};
    int dy[4]={0,1,0,-1};
    void bfs(int s,int t)
    {
    	queue<pair<int,int> >que;
    	que.push({s,t});
    	v[s][t]=1;
    	while(que.size()>0)
    	{
    		int i=que.front().first,j=que.front().second; que.pop();
    		for(int k=0;k<=3;k++)
    		{
    			int x=i+dx[k],y=j+dy[k];
    			if(x>=1&&x<=n&&y>=1&&y<=m && v[x][y]==0&&ch[x][y]!='0')
    			{
    				v[x][y]=1;
    				que.push({x,y});
    			}
    		}
    	}
    }
    int main()
    {
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)cin>>ch[i]+1;
    	
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=m;j++)
    			if(v[i][j]==0&&ch[i][j]!='0')
    			{
    				++num;
    				bfs(i,j);
    			}
    	cout<<num;
    
    	return 0;
    }
    
    
    • 0
      @ 2022-11-8 17:10:19
      #include <bits/stdc++.h>
      using namespace std;
      int n, m;
      char g[105][105];
      
      queue<pair<int, int>> q;
      int dx[] = {-1, 1, 0, 0};
      int dy[] = {0, 0, -1, 1};
      void gao(int x, int y) // 把 x,y 相连的 1~9 都改成 0
      {
          q.push(make_pair(x, y));
          g[x][y] = '0';
          while (!q.empty())
          {
              pair<int, int> now = q.front();
              q.pop();
              for (int i = 0; i < 4; i++)
              {
                  int nx = now.first + dx[i];
                  int ny = now.second + dy[i];
                  if (1 <= nx && nx <= n &&
                      1 <= ny && ny <= m &&
                      g[nx][ny] > '0')
                  {
                      q.push(make_pair(nx, ny));
                      g[nx][ny] = '0';
                  }
              }
          }
      }
      int main()
      {
          cin >> n >> m;
          for (int i = 1; i <= n; i++)
              for (int j = 1; j <= m; j++)
                  cin >> g[i][j];
          int ans = 0;
          for (int i = 1; i <= n; i++)
              for (int j = 1; j <= m; j++)
                  if ('0' < g[i][j])
                  {
                      ans++;
                      gao(i, j);
                  }
          cout << ans << "\n";
          return 0;
      }
      
      • 1

      信息

      ID
      548
      时间
      1000ms
      内存
      128MiB
      难度
      2
      标签
      (无)
      递交数
      92
      已通过
      57
      上传者