一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1462|回复: 17
收起左侧

[算法题] find shortest path in matrix

[复制链接] |试试Instant~ |关注本帖
zyy6799 发表于 2015-12-23 11:48:50 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 zyy6799 于 2015-12-23 13:30 编辑

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

hulahu 发表于 2015-12-23 12:24:40 | 显示全部楼层
题目具题说说麻
回复 支持 反对

使用道具 举报

 楼主| zyy6799 发表于 2015-12-23 12:30:25 | 显示全部楼层
hulahu 发表于 2015-12-23 12:24
题目具题说说麻

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

回复 支持 反对

使用道具 举报

hulahu 发表于 2015-12-23 12:36:06 | 显示全部楼层
https://leetcode.com/problems/minimum-path-sum/ 这一道, 用dp 就可以了。。
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-12-23 12:37:01 | 显示全部楼层
本帖最后由 blactangeri 于 2015-12-24 00:18 编辑

这个dp是不行的  因为一开始你并没说允许前进的方向
回复 支持 反对

使用道具 举报

 楼主| zyy6799 发表于 2015-12-23 12:39:00 | 显示全部楼层
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.
回复 支持 反对

使用道具 举报

wtcupup 发表于 2015-12-23 12:43:41 | 显示全部楼层
这道题不用想太复杂,用queue做能自动找到shortest path
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-12-23 12:46:14 | 显示全部楼层
you are right. But I think the logic is pretty like this https://leetcode.com/problems/unique-paths-ii/, DP should works.

回复 支持 反对

使用道具 举报

tltzhsajsdr 发表于 2015-12-23 12:49:20 | 显示全部楼层
我觉得你问的是如何输出这k steps,他们回的好像是如何得到最短的步数,还有人回答dp的偏的更远了。
如果我没理解错你的问题的话,用queue bfs,BFS的时候,每次记录当前这一个位置是从哪里过来的,找到target以后,逆向按照上一步的位置追溯回起始点,这条路就是最短路径。
回复 支持 反对

使用道具 举报

 楼主| zyy6799 发表于 2015-12-23 13:19:07 | 显示全部楼层
hulahu 发表于 2015-12-23 12:36
https://leetcode.com/problems/minimum-path-sum/ 这一道, 用dp 就可以了。。

我觉得还是应该用BFS吧~求问dp怎么做呀~
回复 支持 反对

使用道具 举报

 楼主| zyy6799 发表于 2015-12-23 13:20:34 | 显示全部楼层
tltzhsajsdr 发表于 2015-12-23 12:49
我觉得你问的是如何输出这k steps,他们回的好像是如何得到最短的步数,还有人回答dp的偏的更远了。
如果 ...

对!!现在比较纠结的是Queue 的话,怎么找相邻的点?

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

  }
}
回复 支持 反对

使用道具 举报

 楼主| zyy6799 发表于 2015-12-23 13:22:06 | 显示全部楼层
zyy6799 发表于 2015-12-23 13:20
对!!现在比较纠结的是Queue 的话,怎么找相邻的点?

while(!Q.empty()){

如果不定义
struct node{
};之类的话
回复 支持 反对

使用道具 举报

 楼主| zyy6799 发表于 2015-12-23 13:30:17 | 显示全部楼层


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

#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;
}
回复 支持 反对

使用道具 举报

stellari 发表于 2015-12-23 15:59:29 | 显示全部楼层
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。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-12-23 16:06:36 | 显示全部楼层
zyy6799 发表于 2015-12-23 13:20
对!!现在比较纠结的是Queue 的话,怎么找相邻的点?

while(!Q.empty()){

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

使用道具 举报

 楼主| zyy6799 发表于 2015-12-23 23:58:51 | 显示全部楼层
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.
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-12-24 02:55:18 | 显示全部楼层
stellari 发表于 2015-12-23 15:59
unique paths和这道题的最大分歧是在于前者只能“向右向左”移动,而此处是可以“四个方向”移动。所以, ...

我又犯二了, 多谢大神指点。。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-12-25 17:40:38 | 显示全部楼层
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是从哪里来的?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 17:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表