2 条题解

  • 1
    @ 2025-6-18 20:00:01

    深搜写法

    #include <bits/stdc++.h>
    using namespace std;
    int n, m;
    char g[115][115];
    int dx[8] = {-1, 1, 0, 0, -1, 1, -1, 1};
    int dy[8] = {0, 0, -1, 1, -1, -1, 1, 1};
    // 把(x,y)这个位置相连的水全都清空
    void dfs(int x, int y)
    {
        g[x][y] = '.';
        for (int i = 0; i < 8; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (1 <= xx && xx <= n &&
                1 <= yy && yy <= m &&
                g[xx][yy] == 'W')
                dfs(xx, yy);
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        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 (g[i][j] == 'W')
                {
                    ans++;
                    dfs(i, j);
                }
        cout << ans;
        return 0;
    }
    
    • 0
      @ 2022-11-8 16:27:45

      广搜写法

      两个队列分别表示两个坐标

      #include <bits/stdc++.h>
      using namespace std;
      int n, m;
      char g[115][115];
      // 把与 (x,y) 连通的 'W' 都改为 '.'
      int dx[8] = {0, 0, 1, -1, -1, -1, 1, 1};
      int dy[8] = {1, -1, 0, 0, -1, 1, -1, 1};
      queue<int> qx, qy;
      void bfs(int x, int y)
      {
          // 起点入队
          qx.push(x);
          qy.push(y);
          g[x][y] = '.';
          // 队列非空就继续搜
          while (!qx.empty())
          {
              // 取出队头
              int now_x = qx.front();
              int now_y = qy.front();
              qx.pop();
              qy.pop();
              // 考虑 now_x,now_y 能走到哪儿
              for (int i = 0; i < 8; i++)
              {
                  // now_x,now_y 的第 i 个方向的点是 next_x,nextY
                  int next_x = now_x + dx[i];
                  int next_y = now_y + dy[i];
                  // 能走到,且没走过
                  if (1 <= next_x && next_x <= n &&
                      1 <= next_y && next_y <= m &&
                      g[next_x][next_y] == 'W')
                  {
                      qx.push(next_x);
                      qy.push(next_y);
                      g[next_x][next_y] = '.';
                  }
              }
          }
      }
      int main()
      {
          ios::sync_with_stdio(false);
          cin.tie(0);
          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 (g[i][j] == 'W')
                  {
                      ans++;
                      bfs(i, j); // 把与 i,j 连通的 'W' 都改为 '.'
                  }
              }
          cout << ans;
          return 0;
      }
      

      用 vis 标记有没有被统计过

      #include <bits/stdc++.h>
      using namespace std;
      const int MAXN = 110;
      int n, m;
      char a[MAXN + 5][MAXN + 5];
      int dx[] = {-1, 1, 0, 0, -1, 1, -1, 1};
      int dy[] = {0, 0, -1, 1, -1, -1, 1, 1};
      // 每个位置有没有被统计过,false 表示没有被统计过
      bool vis[MAXN + 5][MAXN + 5];
      // 广搜的队列
      queue<pair<int, int>> q;
      // 把 (x,y) 相连的 W 全都标记为统计过了
      void bfs(int x, int y)
      {
          // 起点入队
          q.push(make_pair(x, y));
          vis[x][y] = true;
          // 只要还有东西要改,就改
          while (!q.empty())
          {
              // 取出队头
              pair<int, int> now = q.front();
              q.pop();
              int nowX = now.first;
              int nowY = now.second;
              // 检查当前位置八连通的所有位置
              for (int i = 0; i < 8; i++)
              {
                  int nxtX = nowX + dx[i];
                  int nxtY = nowY + dy[i];
                  // 在范围内、是 W、没统计过,就继续搜
                  if (1 <= nxtX && nxtX <= n &&
                      1 <= nxtY && nxtY <= m &&
                      a[nxtX][nxtY] == 'W' &&
                      vis[nxtX][nxtY] == false)
                  {
                      q.push(make_pair(nxtX, nxtY));
                      vis[nxtX][nxtY] = true;
                  }
              }
          }
      }
      int main()
      {
          ios::sync_with_stdio(false);
          cin.tie(0);
          cin >> n >> m;
          for (int i = 1; i <= n; i++)
              for (int j = 1; j <= m; j++)
                  cin >> a[i][j];
      
          int ans = 0;
          for (int i = 1; i <= n; i++)
          {
              for (int j = 1; j <= m; j++)
              {
                  if (a[i][j] == 'W' && !vis[i][j])
                  {
                      ans++;
                      // 把这个水洼全都标记为被算过了
                      bfs(i, j);
                  }
              }
          }
          cout << ans;
          return 0;
      }
      

      直接改成 .

      #include <bits/stdc++.h>
      using namespace std;
      int n, m, ans;
      char g[115][115];
      //广搜
      bool vis[115][115];
      struct Point
      {
          int x, y;
      };
      queue<Point> q;
      int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
      int dy[] = {1, -1, 1, -1, 0, 0, 1, -1};
      void bfs(int sx, int sy)
      {
          //初始化
          memset(vis, false, sizeof(vis));
          while (!q.empty())
              q.pop();
          //起点入队
          q.push((Point){sx, sy});
          vis[sx][sy] = true;
          while (!q.empty())
          {
              //取出队头
              Point now = q.front();
              q.pop();
              //枚举能到达的所有点
              for (int i = 0; i < 8; i++)
              {
                  int nx = now.x + dx[i];
                  int ny = now.y + dy[i];
                  // (now.x, now.y) -> (nx, ny)
                  if (1 <= nx && nx <= n &&
                      1 <= ny && ny <= m &&
                      !vis[nx][ny] &&
                      g[nx][ny] == 'W')
                  {
                      q.push((Point){nx, ny});
                      g[nx][ny] = '.';
                      vis[nx][ny] = true;
                  }
              }
          }
      }
      int main()
      {
          cin >> n >> m;
          for (int i = 1; i <= n; i++)
              for (int j = 1; j <= m; j++)
                  cin >> g[i][j];
          ans = 0;
          for (int i = 1; i <= n; i++)
              for (int j = 1; j <= m; j++)
                  if (g[i][j] == 'W')
                  {
                      ans++;
                      //把这个点对应的水洼抽干
                      bfs(i, j);
                  }
          cout << ans << endl;
          return 0;
      }
      
      • 1

      信息

      ID
      468
      时间
      1000ms
      内存
      128MiB
      难度
      5
      标签
      (无)
      递交数
      190
      已通过
      71
      上传者