将一段dfs代码换方法实现

Question

能将下面的代码换一种算法实现吗

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x,y;
};
int n,m,cc,dd,ww,ee,dp[1010][1010],tx[4]={0,1,0,-1},ty[4]={1,0,-1,0};
char c[1010][1010];
bool b[1010][1010],f;
void dfs(int x,int y,int o)
{
    dp[x][y]=o;
    for(int i=max(x-2,1);i<=min(x+2,n);i++)
        for(int j=max(y-2,1);j<=min(y+2,m);j++)
        {
            if(i==x&&j==y) continue;
            if(dp[i][j]<=o) continue;
            if(c[i][j]=='#') continue;
            dp[i][j]=o+1;
        }
    for(int i=0;i<4;i++)
    {
        int nx=tx[i]+x;
        int ny=ty[i]+y;
        if(nx<1||nx>n||ny<1||ny>m||c[nx][ny]=='#'||b[nx][ny]==1) continue;
        b[nx][ny]=1;
        dfs(nx,ny,o);
    }
}
int main()
{
    memset(dp,127/3,sizeof(dp));
    cin>>n>>m>>cc>>dd>>ww>>ee;
    dp[cc][dd]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%s",&c[i][j]); 
        }
    for(int k=0;;k++)
    {
        f=0;
        if(dp[ww][ee]<1000000) 
        {
            cout<<dp[ww][ee]<<endl;
            return 0;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(dp[i][j]==k&&b[i][j]==0) dfs(i,j,k),f=1;
            }
        if(f==0) break;
    }
    cout<<-1;
    return 0;
}

Answer 1

🕒下午好，题主！目前：🟢[在线]
📢参考GPT-4o mini 模型、由清水白石008整理提供！
📣今日金句：“成功是由许多小的努力汇聚而成的。”** — 文森特·梵高

当然可以！你提供的代码使用了深度优先搜索（DFS）来遍历一个网格并更新每个位置的状态。我们可以将其转换为广度优先搜索（BFS）来实现相同的功能。BFS 通常更适合处理最短路径问题，因为它会逐层扩展，确保在找到目标时路径是最短的。

以下是将你的 DFS 代码转换为 BFS 的实现：

#include <bits/stdc++.h>
using namespace std;

struct node {
    int x, y;
};

int n, m, cc, dd, ww, ee, dp[1010][1010];
char c[1010][1010];
bool b[1010][1010];

int main() {
    memset(dp, 127 / 3, sizeof(dp));
    cin >> n >> m >> cc >> dd >> ww >> ee;
    dp[cc][dd] = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%s", &c[i][j]);
        }

    queue<node> q;
    q.push({cc, dd});
    b[cc][dd] = true;

    for (int k = 0; ; k++) {
        bool f = false;
        if (dp[ww][ee] < 1000000) {
            cout << dp[ww][ee] << endl;
            return 0;
        }

        // BFS for the current distance k
        int size = q.size();
        for (int i = 0; i < size; i++) {
            node current = q.front();
            q.pop();

            // Explore the 5x5 area around the current node
            for (int x = max(current.x - 2, 1); x <= min(current.x + 2, n); x++) {
                for (int y = max(current.y - 2, 1); y <= min(current.y + 2, m); y++) {
                    if (x == current.x && y == current.y) continue;
                    if (dp[x][y] <= k) continue;
                    if (c[x][y] == '#') continue;

                    dp[x][y] = k + 1;
                    if (!b[x][y]) {
                        b[x][y] = true;
                        q.push({x, y}); // Add to queue for BFS
                    }
                }
            }
        }

        // Clear the visited array for the next iteration
        memset(b, 0, sizeof(b));
    }

    cout << -1;
    return 0;
}

主要修改点

1. 使用队列：我们使用 queue<node> 来实现 BFS。每次从队列中取出一个节点，处理它的邻居。

2. 遍历 5x5 区域：在 BFS 中，我们仍然遍历当前节点周围的 5x5 区域（即 max(x-2, 1) 到 min(x+2, n)），并更新 dp 数组。

3. 更新和入队：如果找到一个可以更新的节点，我们将其标记为已访问并将其加入队列。

4. 清空访问标记：在每次 BFS 迭代结束后，我们清空访问标记数组 b，以便在下一次迭代中重新使用。

总结

通过将 DFS 转换为 BFS，我们可以更有效地处理最短路径问题，确保在找到目标时路径是最短的。请根据你的具体需求进行测试和调整。如果你有其他问题或需要进一步的帮助，请随时告诉我！