c++ - 在网格中找到最短路径的算法
问题描述
背景:
问题来自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;
}
};
解决方案
这不是您将使用 Dijkstra 算法的问题。该算法针对加权图,而您正在处理的问题是unweighted。此外,您使用优先级队列的方式是错误的。默认情况下,C++ 优先级队列将弹出最大的元素,但是由于您为其提供了坐标,这意味着它将弹出具有最大坐标的元素。这显然不是你需要的。事实上,你没有任何东西可以用来排序节点,因为这个问题是关于一个未加权的图。
其次,count
计算您访问的节点总数。这是不对的,因为您肯定还会访问不在您最终找到的最短路径上的节点。
这种问题可以通过标准的深度优先搜索来解决。您可以使用两个向量(不需要堆栈、队列或双端队列,...):第二个向量填充第一个中所有节点的未访问邻居。一旦该循环完成,您将第一个向量替换为第二个,创建一个新的第二个向量,然后重复......直到找到目标节点。您执行此(外部)重复的次数对应于路径的长度。
这是您的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;
}
推荐阅读
- java - 无法在 JPopupMenu 中执行 JMenuItem 操作而不会抛出 java.lang.ClassCastException
- android - 如何完成应用程序并返回上一屏幕
- javascript - React:如何在不改变状态的情况下根据属性过滤状态?
- arrays - 219. Contains Duplicate II - 为什么使用二分查找的解决方案适用于未排序的数组?
- php - 如何在php mysql的单个页面中多次调用存储过程
- c++ - 编写单元测试和使用 for 循环时的最佳方法?
- python - 如何检查python函数是否使用while循环?
- reactjs - 如何将按钮添加到 react-date-range
- python - 基于元数据列出 azure blob - python sdk
- python-3.x - 具有不同进程的多个 tqdm 进度条