问网格中最短路径的算法
EN

Stack Overflow用户

提问于 2020-01-24 17:40:26

回答 1查看 799关注 0票数 0

背景：

问题来自于leetcode

在N×N平方网格中，每个单元格要么是空的(0)，要么是阻塞的(1)。从左上角到右下角的清晰路径具有长度k当且仅当它是由单元格C_1, C_2, ..., C_k组成的，这样：

相邻的信元C_i和C_{i+1}是向8方向连接的(也就是说，它们是不同的，并且共享一个边或角)。
C_1在(0, 0)的位置。有价值的grid[0][0])
C_k在(N-1, N-1)的位置。有价值的grid[N-1][N-1])
如果C_i位于(r, c)，那么grid[r][c]是空的。grid[r][c] == 0)。

从左上角到右下角返回最短的这种清晰路径的长度。如果不存在这样的路径，则返回-1。

问题：

我确信我的算法是正确的，但是对于这个测试用例：

[[0,1,0,0,0],[0,1,0,0,0],[0,0,0,0,1],[0,1,1,1,0],[0,1,0,0,0]]

我得到9，正确的答案是7。下面的代码中有我做错了什么吗？

代码：

class Solution {
public:
    std::vector<std::vector<int>> dirs = {{0,1},{1,0},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if(grid.empty())
            return 0;

        if(grid[0][0] == 1 || grid[grid.size()-1][grid.size()-1] == 1) 
            return -1;


        int m = grid.size(), n = grid[0].size();
        std::pair<int, int> start = {0,0};
        std::pair<int, int> end = {m-1, n-1};
        std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
        std::priority_queue<std::pair<int,int>> q;
        q.push(start);
        visited[start.first][start.second] = true;
        int count = 1;

        while(!q.empty())
        {
            auto cur = q.top();
            q.pop();

            if(cur.first == end.first && cur.second == end.second)
                return count;

            for(auto dir : dirs)
            {
                int x = cur.first, y = cur.second;

                if(isValid(grid, x + dir[0], y + dir[1]))
                    x += dir[0], y += dir[1];

                if(!visited[x][y])
                {
                    visited[x][y] = true;
                    q.push({x,y});
                }
            }
            count++;
        }
        return -1;
    }

    bool isValid(std::vector<std::vector<int>>& grid, int i, int j)
    {
        if(i < 0 || i >= grid.size() || j < 0 || j >= grid[i].size() || grid[i][j] != 0)
            return false;
        return true;
    }
};

c++

algorithm

path-finding

语音识别特惠活动

语音识别准确率高、用于会议内容转写、客服质检等场景，助力企业将本增效

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-01-25 02:55:48

对于这个问题，您可以使用Dijkstra的算法。这个算法是处理加权图，而你正在处理的问题是不加权的。此外，使用优先级队列的方式是错误的。默认情况下，C++优先级队列将弹出最大的元素，但由于提供了它的坐标，这意味着它将弹出具有最大坐标的元素。这显然不是你需要的。实际上，您没有任何可以排序的节点，因为这个问题是关于一个未加权图的。

其次，count正在计算您访问的节点总数。这是不对的，因为您当然也访问了那些不是在您最终找到的最短路径上的节点。

这种问题是用标准的深度优先搜索来解决的。您可以使用两个向量(不需要堆栈、队列或deque，.)：第二个向量由第一个节点中所有节点的未访问邻居填充。这个循环完成后，用第二个向量替换第一个向量，创建一个新的第二个向量，然后重复.直到你找到目标节点。执行此(外部)重复的次数与路径的长度相对应。

下面是您的shortestPathBinaryMatrix函数，需要进行必要的调整，以使其正常工作：

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    if(grid.empty())
        return 0;

    if(grid[0][0] == 1 || grid[grid.size()-1][grid.size()-1] == 1) 
        return -1;

    int m = grid.size(), n = grid[0].size();
    pair<int, int> start = {0,0};
    pair<int, int> end = {m-1, n-1};
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    // no priority queue needed: the graph is not weighted
    vector<std::pair<int,int>> q;
    q.push_back(start);
    visited[start.first][start.second] = true;
    int count = 1;

    while(!q.empty())
    {
        // just iterate the vector and populate a new one
        vector<std::pair<int,int>> q2;
        for(auto const& cur: q) {
            if(cur.first == end.first && cur.second == end.second)
                return count;
            for(auto dir : dirs)
            {
                int x = cur.first, y = cur.second;

                if(isValid(grid, x + dir[0], y + dir[1]))
                    x += dir[0], y += dir[1];

                if(!visited[x][y])
                {
                    visited[x][y] = true;
                    q2.push_back({x,y});
                }
            }
        }
        count++;
        q = q2; // prepare for next iteration
    }
    return -1;
}