题目描述
一图胜千言
算法
找最短路 BFS即可。因为是一层层搜的,所以肯定是最短的。
用的是队列实现。BFS模板。
class Solution {
public:
typedef struct{
int x;
int y;
}Node;
int hh = 0, tt = -1;
Node queue[110 * 110];
int dis[100][100];
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
// printf("%d %d\n", n, m);
if (grid[0][0] == 1 || grid[n - 1][m - 1] == 1) {
return -1;
}
const int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1}; //;x轴(横向)偏移量
const int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; //y轴(竖向)偏移量
// memset(dis, 1, sizeof(dis));
for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < m; j ++ ) {
dis[i][j] = 10010; //初始化
}
}
hh = 0, tt = -1;
tt ++ ;
queue[tt].x = 0;
queue[tt].y = 0;
dis[tt][tt] = 1;
while (hh <= tt) { //BFS开搜
Node sta = queue[hh];
hh ++ ;
if (sta.x == n - 1 && sta.y == m - 1) {
break;
}
for (int i = 0; i < 8; i ++ ) {
int x = sta.x + dx[i], y = sta.y + dy[i]; // 使用x加dx偏移量来实现移动
if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 1) //我想应该是出界 或堵塞的(1的块)跳过
continue;
}
if (dis[x][y] > dis[sta.x][sta.y] + 1) { //如果下一个点比之前的点大(即在后面)
dis[x][y] = dis[sta.x][sta.y] + 1; //说明可以走,我们就走一步。(更新dis答案长度数组)
tt ++ ;
queue[tt].x = x;
queue[tt].y = y;
}
}
}
if (dis[n - 1][m - 1] == 10010) { //[[0]]的情况 返回-1
dis[n - 1][m - 1] = -1;
}
return dis[n - 1][m - 1];
}
};
评论区大神版: set the visited grid as non-empty to avoid revisiting.
把搜过的填成1避免重复搜。
思路真清楚,我准备把你的solution熟读并背诵
def shortestPathBinaryMatrix(grid):
n = len(grid)
if grid[0][0] or grid[n-1][n-1]:
return -1
q = [(0, 0, 1)]
grid[0][0] = 1
for i, j, d in q:
if i == n-1 and j == n-1: return d
for x, y in ((i-1,j-1),(i-1,j),(i-1,j+1),(i,j-1),(i,j+1),(i+1,j-1),(i+1,j),(i+1,j+1)):
if 0 <= x < n and 0 <= y < n and not grid[x][y]:
grid[x][y] = 1
q.append((x, y, d+1))
return -1