1 条题解

  • 0
    @ 2025-10-19 16:29:47

    思路:先堵死坏人周围空地,再检查终点是否可通行;从终点 BFS 标记可达区域,最后验证所有坏人不可达、所有好人可达。

    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define endl '\n'
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    struct node {
        int x, y;
    };
    void solve() {
        char a[60][60];
        node good[3000]; // 好人(G)的坐标数组
        node bad[3000];  // 坏人(B)的坐标数组
        int good_cnt = 0;    // 好人数量
        int bad_cnt = 0;     // 坏人数量
        bool vis[60][60] = {false}; // BFS访问标记
        int n, m;
        cin >> n >> m;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++){
                cin >> a[i][j];
                if(a[i][j] == 'G'){
                    good[good_cnt] = {i, j}; // 结构体赋值
                    good_cnt++;
                }
                else if(a[i][j] == 'B'){
                    bad[bad_cnt] = {i, j};
                    bad_cnt++;
                }
            }
        }
        // 处理坏人周围的空地(堵墙)
        for(int k = 0; k < bad_cnt; k++){
            int x = bad[k].x; 
            int y = bad[k].y;
            // 检查四个方向,空地则堵墙
            if (x - 1 >= 1 && a[x - 1][y] == '.') a[x - 1][y] = '#';
            if (x + 1 <= n && a[x + 1][y] == '.') a[x + 1][y] = '#';
            if (y - 1 >= 1 && a[x][y - 1] == '.') a[x][y - 1] = '#';
            if (y + 1 <= m && a[x][y + 1] == '.') a[x][y + 1] = '#';
        }
        // 特殊情况:终点被堵死
        if(a[n][m] == '#'){
            // 若有好人则无法到达,否则可行
            cout << (good_cnt ? "No" : "Yes") << endl;
            return;
        }
        // BFS:从终点(n,m)出发标记可达区域
        queue<node> q; 
        q.push({n, m});
        vis[n][m] = true;
        while (!q.empty()) {
            node cur = q.front(); 
            q.pop();
            int x = cur.x;
            int y = cur.y;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                if (a[nx][ny] == '#' || vis[nx][ny]) continue;
                vis[nx][ny] = true;
                q.push({nx, ny}); 
            }
        }
        // 检查所有坏人是否不可达终点
        for (int k = 0; k < bad_cnt; k++) {
            int x = bad[k].x;
            int y = bad[k].y;
            if (vis[x][y]) {
                cout << "No" << endl;
                return;
            }
        }
        // 检查所有好人是否都可达终点
        for (int k = 0; k < good_cnt; k++) {
            int x = good[k].x;
            int y = good[k].y;
            if (!vis[x][y]) {
                cout << "No" << endl;
                return;
            }
        }
        // 所有条件满足
        cout << "Yes" << endl;
    }
    
    signed main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        
        int T;
        cin >> T;
        while (T--) solve();
        
        return 0;
    }
    
    • @ 2025-10-19 16:34:48

      C++实现

      #include <bits/stdc++.h>
      using namespace std;
      #define rep(i, l, r) for (int i = l; i <= r; i++)
      #define pii pair<int, int>
      #define int long long
      #define endl '\n'
      int fx[] = {0,0,1,-1};
      int fy[] = {1,-1,0,0};
      void solve() {
          char a[60][60];
          vector<pii> good,bad;
          bool vis[60][60]={0};
          int n,m;cin >> n >> m;
          for(int i = 1; i <= n; i++){
              for(int j = 1; j <= m; j++){
                  cin >> a[i][j];
                  if(a[i][j] == 'G')good.push_back({i,j});
                  if(a[i][j] == 'B')bad.push_back({i,j});  
              }
          }
          for(auto [x,y] : bad){
              if(x-1 >= 1 && a[x-1][y] == '.') a[x-1][y] = '#';
              if(x+1 <= n && a[x+1][y] == '.') a[x+1][y] = '#';
              if(y-1 >= 1 && a[x][y-1] == '.') a[x][y-1] = '#';
              if(y+1 <= m && a[x][y+1] == '.') a[x][y+1] = '#';
          }
          if(a[n][m] == '#'){
              if(!good.empty())cout << "No" << endl;
              else cout << "Yes" << endl;
              return;
          }
          queue<pii> q;
          q.push({n,m});
          vis[n][m] = 1;
          while(!q.empty()){
              auto [x,y] = q.front();q.pop();
              for(int i = 0; i < 4; i++){
                  int nx = x + fx[i]; int ny = y + fy[i];
                  if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
                  if(a[nx][ny] == '#' || vis[nx][ny]) continue;
                  vis[nx][ny] = 1;
                  q.push({nx,ny});
              }
          }
          for(auto [x,y] : bad)if(vis[x][y]){cout << "No" << '\n'; return;}
          for(auto [x,y] : good)if(!vis[x][y]){cout << "No" << '\n'; return;}
          cout << "Yes" << '\n';
      }
      signed main() {
          ios::sync_with_stdio(0);
          cin.tie(0);
          cout.tie(0);
          int T = 1;
          cin >> T;
          while (T--)
              solve();
          return 0;
      }
      
  • 1

信息

ID
1143
时间
1000ms
内存
256MiB
难度
8
标签
递交数
13
已通过
6
上传者