0

有人可以帮我吗？它给了我一个错误的号码。matrix[i][j].spath 填充了正确的值，但是当我返回任意两个节点之间的最短路径时，它给了我一个错误的数字。编译器给了我这个

警告：控制到达非无效函数的结尾

但是我检查是否到达终点的 if 语句将始终执行 return 语句，因为我在 main() 中设置了结束坐标。但是我注意到，当我在函数末尾添加 return 1 或返回任何内容时，它会给出正确的结果。这是一种规则还是什么？我写了一个像这样的函数，其中我有一个 if 语句和唯一的 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;


    return 0;
}
4

3 回答 3

0

About the warning :

Your code is not protected against bad input : if end is outside your n x m grid, or is on a "wall", or if there is no path from start to end your function will exit without executing a return statement.

The compiler has no way of predicting what input will be fed to the function.

于 2013-10-09T13:26:24.493 回答
0

As you noticed, the problem is that it misses a return statement. You may know that it will always go through the return in the if statement, but the compiler doesn't, hence the warning. You supposed the input was correct, but you should "never trust user input". Never Ever.

There should always be a return statement for all routes the execution might take in your non-void function.

于 2013-10-09T13:26:42.597 回答
0

看来您正在编写 BFS。这是我的代码：

#include"stdio.h"
#include"string.h"
#include"queue"
using namespace std;
#define N 200
int n,m;
int move[][2]={{0,1},{1,0},{0,-1},{-1,0}};
struct node
{
    node(int _x=0,int _y=0)
    {
        x=_x,y=_y;
    }
    int x,y;    //mark the Coord of the node
};
int data[N][N];//store data.
bool map[N][N]; //mark whether the node is visited.
int input()//input & initialize the array
{
    memset(map,false,sizeof(map));
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
    {
        int t;
        scanf("%d",&t);
        data[i][j]=t;
        map[i][j]=false;
    }
    return 0;
}
bool judge(node x)
{
    if(x.x<n&&x.x>=0&&x.y<m&&x.y>=0) return true;
    return false;
}
int shortest_path(node s,node e)
{
    queue<int>dist;//means  'spath' in your code.
    int dst=0;
    queue<node>q;
    q.push(s);
    map[s.x][s.y]=true;
    dist.push(0);
    node v,c;
    while(!q.empty())
    {
        v=q.front();
        q.pop();
        dst=dist.front();
        dist.pop();
        for(int i=0;i<4;i++)
        {
            c.x=v.x+move[i][0];
            c.y=v.y+move[i][1];
            if(judge(c)&&!map[c.x][c.y])
            {
                dist.push(dst+1);
                q.push(c);
                map[c.x][c.y]=true;
                if(c.x==e.x&&c.y==e.y)
                    return dst+1;
            }
        }
    }
    return -1;//if the path not found return -1;
};
int main()
{
    input();
    node s(0,0),e(4,4);
    printf("%d\n",shortest_path(s,e));
    return 0;
}

输入应该是：n>=5 m>=5，因为终点是(4,4)。和一个 n*m 矩阵。

于 2013-10-09T13:47:55.523 回答