关于#c++#的问题：为啥输出sum和bfs(x,y)得到的值不一样还有提交答案还说我数组越界不懂#include <iostream>（相关搜索：迷宫问题）

Question

为啥输出sum和bfs(x,y)得到的值不一样
还有提交答案说我数组越界不懂

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int, int>pii;
queue<pii>q;
int dxx[10] = { -1,0,1,0};
int dyy[10] = {0,1,0,-1};
int t, n, m;
char tmp;
int a[105][105];
int x, y;
int ex, ey;
int sum;
int dist[105][105];
int bfs(int x, int y)
{
    memset(dist, -1, sizeof dist);
    q.push({ x,y });
    dist[x][y] = 0;
    while (!q.empty())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            
            int dx = t.first + dxx[i];
            int dy = t.second + dyy[i];
            if (dx<1 || dy<1 || dx>n || dy>m)continue;
            if (a[dx][dy] == 0)continue;
            if (dist[dx][dy] > 0)continue;
            dist[dx][dy] = dist[t.first][t.second] + 1;
            q.push({ dx,dy });
        
            if (dist[ex][ey]>0)return dist[ex][ey];
        }
    }
}
int    main()
{
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        memset(a, 0, sizeof(a));
        
        cin >> n >> m;
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= m; k++)
            {
                cin >> tmp;
                if (tmp == 'S')
                {
                    x = j;
                    y = k;
                    a[j][k] = 1;
                }
                if (tmp == 'E')
                {
                    ex = j;
                    ey = k;
                    a[j][k] = 1;
                }
                if (tmp == '-')a[j][k] = 1;
                if (tmp == '#')a[j][k] = 0;
            }
        }
        sum = bfs(x, y);
        if (sum > 0)cout << bfs(x,y);
        else cout << "-1";
    }
    return 0;
}

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

你的代码中存在一些问题，我将为你解释并提供修改后的代码。

问题1：你在bfs函数中使用了全局变量dist，这可能会导致在多次调用bfs时出现问题。建议将dist作为局部变量传递给bfs函数。

问题2：你在bfs函数的最后返回的是dist[ex][ey]，但是这个值可能没有被更新，因为你可能没有遍历到终点。你应该在遍历过程中检查是否到达终点，并在到达终点时返回正确的距离。

问题3：你在main函数中调用了两次bfs(x, y)，这是不必要的。你可以在第一次调用bfs时保存结果，然后在需要的地方使用它。

修改后的代码如下：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int, int>pii;
queue<pii>q;
int dxx[4] = { -1,0,1,0};
int dyy[4] = {0,1,0,-1};
int t, n, m;
char tmp;
int a[105][105];
int x, y;
int ex, ey;

int bfs(int x, int y)
{
    int dist[105][105];
    memset(dist, -1, sizeof dist);
    q.push({ x,y });
    dist[x][y] = 0;
    while (!q.empty())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int dx = t.first + dxx[i];
            int dy = t.second + dyy[i];
            if (dx<1 || dy<1 || dx>n || dy>m)continue;
            if (a[dx][dy] == 0)continue;
            if (dist[dx][dy] > 0)continue;
            dist[dx][dy] = dist[t.first][t.second] + 1;
            q.push({ dx,dy });
            if (dx == ex && dy == ey)return dist[ex][ey];
        }
    }
    return -1;
}

int main()
{
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        memset(a, 0, sizeof(a));
        cin >> n >> m;
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= m; k++)
            {
                cin >> tmp;
                if (tmp == 'S')
                {
                    x = j;
                    y = k;
                    a[j][k] = 1;
                }
                if (tmp == 'E')
                {
                    ex = j;
                    ey = k;
                    a[j][k] = 1;
                }
                if (tmp == '-')a[j][k] = 1;
                if (tmp == '#')a[j][k] = 0;
            }
        }
        int sum = bfs(x, y);
        if (sum > 0)cout << sum << endl;
        else cout << "-1" << endl;
    }
    return 0;
}

这个修改后的代码应该可以解决你的问题。