1

为什么这段代码不起作用?对于此输入:

5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

它为给定顶点的最短路径输出奇怪的数字,但矩阵没问题(它包含到矩阵中每个单元格的最短路径)。但是如果我在函数最短路径的末尾添加return 1;或其他东西,那么它会输出正确的解决方案。return有人可以告诉我代码有什么问题吗?

#include <iostream>
#include <queue>

using namespace std;

struct node
{
    int x,y,spath,val;
}v,c;

node mat[100][100];
int dy[] = {-1,1,0,0}, dx[] = {0,0,-1,1}, n, m;

void input()
{
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> mat[i][j].val;
            mat[i][j].spath = 0;
        }
    }
}

int shortest_path(node start, node end)
{
    queue<node> q;
    q.push(start);
    mat[start.y][start.x].val = 1;

    while (!q.empty())
    {
        v = q.front();
        q.pop();

        for (int i=0; i<4; i++) {
            c.y = v.y + dy[i];
            c.x = v.x + dx[i];

            if (c.y == end.y && c.x == end.x) {
                return mat[v.y][v.x].spath + 1;
            }
            else if (c.y >=0 && c.y < n && c.x >=0 && c.x < m && mat[c.y][c.x].val == 0)
                {
                    mat[c.y][c.x].val = 1;
                    mat[c.y][c.x].spath = mat[v.y][v.x].spath + 1;
                    q.push(c);
                }
        }
    }
}

int main()
{
    node start,end;
    start.x = start.y = 0;
    end.y = end.x = 4;
    input();
    cout << shortest_path(start,end) << endl;

    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cout << mat[i][j].spath;
        }
        cout << endl;
    }
    return 0;
}
4

0 回答 0