find shortest path in matrix

这道题大伙怎么做的呀？ 虽然知道用BFS来做， 但是一直没做出来。有没有大神可以交流一下呀！

我在网上找了一下，找到了这个代码觉得还不错，稍微改了一下

#include <iostream>
#include <vector>

using namespace std;

int dfs(vector<vector<int>>& maze, pair<int, int> p,int endx,int endy)
{
    vector <pair<pair<int, int>, int> > v;
    int n = (int)maze.size();
    int m = (int)maze[0].size();
    vector<vector<bool>> visited(n,vector<bool> (m, false));
    int x, y, k = 0;
    pair <pair<int, int>, int> mj;
    pair <pair<int, int>, int> z;
    pair <int, int> l;
    z = make_pair(make_pair(p.first, p.second), 0);
    v.push_back(z);
    while(v.size() != 0)
    {
        mj = v.front();
        l = mj.first;
        x = l.first;
        y = l.second;
        k = mj.second;
        v.erase(v.begin());
        if (x == endx && y == endy) {
            return k;
        }
        if((maze[x+1][y] == 0 || (x + 1 == endx && y == endy)) && (!visited[x+1][y]))
        {
            v.push_back(make_pair(make_pair(x+1, y), k+1));
            visited[x+1][y] = true;
        }
        if((maze[x][y+1] == 0 || (x == endx && y + 1 == endy)) && (!visited[x][y+1]))
        {
            v.push_back(make_pair(make_pair(x, y+1), k+1));
            visited[x][y+1] = true;
        }
        if((maze[x-1][y] == 0 || (x - 1 == endx && y == endy)) && (!visited[x-1][y]))
        {
            v.push_back(make_pair(make_pair(x-1, y), k+1));
            visited[x-1][y] = true;
        }
        if((maze[x][y-1] == 0 || (x == endx && y - 1 == endy)) &&(!visited[x][y-1]))
        {
            v.push_back(make_pair(make_pair(x, y-1), k+1));
            visited[x][y-1] = true;
        }
    }
    return k;
}

int main()
{
    int n, m;
    pair <int, int> p;
    int s;
    cin >> n;
    cin >> m;
    vector<vector<int>> maze(n,vector<int> (m,0));
    int startx = 1,starty = 2;
    int endx = 2,endy = 5;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> s;
            maze[j] = s;
            if(i == startx && j == starty){
                p = make_pair(i, j);
            }
        }
    }

    cout << dfs(maze, p, endx, endy) << endl;
    return 0;
}

hulahu 发表于 2015-12-23 12:46
you are right. But I think the logic is pretty like this https://leetcode.com/problems/unique-paths- ...

unique paths和这道题的最大分歧是在于前者只能“向右向左”移动，而此处是可以“四个方向”移动。所以，本题适合用BFS来做，而不是类似于unique path的DP。当然，在BFS的过程当中我们也要注意不要重复处理节点，但是单凭这点一般还是不会称这种算法为DP。

zyy6799 发表于 2015-12-23 23:58
谢谢谢谢！太厉害了！！
还有个问题求教，如果不是四个方向，而是八个方向(x+2,y-1),(x-2,y-1),(x+2,y+1 ...

是的，不过我建议你不要“手写”这8个方向的代码，而是把像每个方向的偏移量都存到一个vector<pair<int, int>> (8)中，这样用一个循环即可处理任意多的方向。

不过，8个方向的偏移量为什么变成了(x+2,y-1)……？+2是从哪里来的？

题目具题说说麻

hulahu 发表于 2015-12-23 12:24
题目具题说说麻

给定一个二维矩阵matrix[M][N],不能走的标记成1。
再给出起点的横纵坐标xstart,ystart, 终点的横纵坐标xstart,xend.
求出矩阵起点到终点的最短路径~

https://leetcode.com/problems/minimum-path-sum/ 这一道， 用dp 就可以了。。

这个dp是不行的  因为一开始你并没说允许前进的方向

hulahu 发表于 2015-12-23 12:36
https://leetcode.com/problems/minimum-path-sum/ 这一道， 用dp 就可以了。。

谢谢你的热心回复呀~
但是我问的不是这个呢~
The task was to find the shortest path between x1,y1 and x2,y2 in a maze. You can move horizontally and vertically, where 1 is a wall and 0 is free space. output is k shortest steps to move from the start point to end point.

这道题不用想太复杂，用queue做能自动找到shortest path

you are right. But I think the logic is pretty like this https://leetcode.com/problems/unique-paths-ii/, DP should works.

我觉得你问的是如何输出这k steps，他们回的好像是如何得到最短的步数，还有人回答dp的偏的更远了。
如果我没理解错你的问题的话，用queue bfs，BFS的时候，每次记录当前这一个位置是从哪里过来的，找到target以后，逆向按照上一步的位置追溯回起始点，这条路就是最短路径。

hulahu 发表于 2015-12-23 12:36
https://leetcode.com/problems/minimum-path-sum/ 这一道， 用dp 就可以了。。

我觉得还是应该用BFS吧~求问dp怎么做呀~