find shortest path in matrix

tltzhsajsdr 发表于 2015-12-23 12:49
我觉得你问的是如何输出这k steps，他们回的好像是如何得到最短的步数，还有人回答dp的偏的更远了。
如果 ...

对！！现在比较纠结的是Queue 的话，怎么找相邻的点？

while(!Q.empty()){
   for(){

  }
}

zyy6799 发表于 2015-12-23 13:20
对！！现在比较纠结的是Queue 的话，怎么找相邻的点？

while(!Q.empty()){

如果不定义
struct node{
};之类的话

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

#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 13:20
对！！现在比较纠结的是Queue 的话，怎么找相邻的点？

while(!Q.empty()){

不自己定义数据结构的话，常见的方法有2：一是用一个pair，就像你找到的那段代码那样；还有就是像MATLAB一样，把一对(x, y)下标映射成一个一维索引ind. 但是后者在找相邻点的时候要涉及一些数学计算，可能会导致代码可读性变差。

stellari 发表于 2015-12-23 16:06
不自己定义数据结构的话，常见的方法有2：一是用一个pair，就像你找到的那段代码那样；还有就是像MATLAB ...

谢谢谢谢！太厉害了！！
还有个问题求教，如果不是四个方向，而是八个方向(x+2,y-1),(x-2,y-1),(x+2,y+1),(x-2,y-1)....这样的是不是也是一样的思路.只是把pair换成这八个，BFS.

stellari 发表于 2015-12-23 15:59
unique paths和这道题的最大分歧是在于前者只能“向右向左”移动，而此处是可以“四个方向”移动。所以， ...

我又犯二了， 多谢大神指点。。

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是从哪里来的？