bfs求类似于连通图的问题

Question

希望解决oibh 被突来的洪水淹没了，还好 oibh 总部有在某些重要的地方起一些围墙。用 * 号表示，而一个四面被围墙围住的区域洪水是进不去的。

oibh 总部内部也有许多重要区域，每个重要区域在图中用一个 0 表示。

现在给出 oibh 的围墙建设图，问有多少个没被洪水淹到的重要区域。的问题，以下代码可以通过样例，但是全wa了不知道为什么

#include<iostream>
using namespace std;
const int N=509;
char g[N][N];
int n,m;
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>g[i][j];
        }
    }
    long long count=0,flag=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='0'){
            
                for(int k=0;k<4;k++){
                    int nx=i+dx[k];
                    int ny=j+dy[k];
                    if(nx<0||nx>=n||ny<0||ny>=m)  {
                        flag=0;
                        continue;
                    }
                    if(g[nx][ny]!='*') {
                        flag=0;
                        continue;
                    }
                    
                }
                if(flag==1) count++;
                flag=1;
            }
        }
    }
    cout<<count<<endl;
    return 0;
}

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

问题概括

这个问题的目的是要计算在给定的二维地图上，有多少个被围墙完全包围的区域（用0表示的重要区域）没有被洪水淹没。地图上用'*'表示围墙，用'0'表示重要区域。一个区域被认为是被洪水淹没的，如果它不是四面都被围墙围住。

问题出现原因

问题出现的原因可能是由于代码中没有正确地使用广度优先搜索（BFS）算法来遍历并标记所有未被洪水淹没的重要区域。代码中使用了四连通性检查，但并没有实现一个完整的BFS过程来确保所有连通的未淹没区域都被计数。

问题解决方案

为了解决这个问题，我们需要实现一个BFS算法，从每个未被淹没的重要区域（'0'）开始，检查其周围的围墙（'*'），如果一个区域的所有四个方向都被围墙包围，则将其计数，并继续BFS搜索直到所有连通的未淹没区域都被访问过。

提供代码

以下是修改后的代码，实现了BFS算法来解决这个问题：

#include<iostream>
#include<queue>
using namespace std;
const int N=509;
char g[N][N];
bool visited[N][N];
int n,m;
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    visited[x][y] = true;
    while (!q.empty()) {
        auto curr = q.front(); q.pop();
        int x = curr.first, y = curr.second;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny] || g[nx][ny] != '*') continue;
            q.push(make_pair(nx, ny));
            visited[nx][ny] = true;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>g[i][j];
            visited[i][j] = false;
        }
    }
    long long count=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='0' && !visited[i][j]) {
                bfs(i, j);
                count++;
            }
        }
    }
    cout<<count<<endl;
    return 0;
}

代码运行方式

这段代码是C++编写的，需要一个支持C++的编译器，如g++。编译和运行的命令如下：

g++ -o bfs bfs.cpp
./bfs

其中bfs.cpp是你的源代码文件名。

代码预期运行结果

如果输入的地图数据是正确的，并且地图中存在未被洪水淹没的重要区域，程序将输出这些区域的数量。

推荐相关链接

• C++ BFS Tutorial
• C++ STL queue
• BFS for Connected Components

这些链接提供了BFS算法的基础知识，以及如何在C++中使用STL中的queue来实现BFS。