当前位置: 首页 > >

[LeetCode] 1091. Shortest Path in Binary Matrix

发布时间:

LeetCode刷题记录


传送门


Description







In an N by N square grid, each cell is either empty (0) or blocked (1).


A?clear?path from top-left to bottom-right?has length?k?if and only if it is composed of cells?C_1, C_2, ..., C_k?such that:


Adjacent cells?C_i?and?C_{i+1}?are connected 8-directionally (ie., they are different and?share an edge or corner)C_1?is at location?(0, 0)?(ie. has value?grid[0][0])C_k?is at location?(N-1, N-1)?(ie. has value?grid[N-1][N-1])If?C_i?is located at?(r, c), then?grid[r][c]?is empty (ie.?grid[r][c] ==?0).

Return the length of the shortest such clear path from top-left to bottom-right.? If such a path does not exist, return -1.


?


Example 1:




?



Note:


    1 <= grid.length == grid[0].length <= 100grid[r][c]?is?0?or?1








思路

题意:给定一个N阶方阵,从左上角走到右下角最短距离是多少,每个格子每次可以选择与其相邻的其他八个格子之一进行行走。


题解:bfs得到最短距离



?



static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();

class Solution {
public:
int shortestPathBinaryMatrix(vector>& grid) {
int size = grid.size();
int dis[size + 5][size + 5];
bool vis[size + 5][size + 5];
memset(vis, false, sizeof(vis));
memset(dis, 0x3f3f3f3f, sizeof(dis));

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
queue>que;
if (grid[0][0] == 0){
que.push(make_pair(0, 0));
dis[0][0] = 1;
vis[0][0] = true;
}

while(!que.empty()){
pairp = que.front();
que.pop();

if (p.first == size - 1 && p.second == size - 1){
break;
}

for (int i = 0; i < 8; i++){
int nx = p.first + dx[i], ny = p.second + dy[i];
if (nx >= 0 && nx < size && ny >= 0 && ny < size && grid[nx][ny] == 0){
if (dis[nx][ny] >= dis[p.first][p.second] + 1 && !vis[nx][ny]){
dis[nx][ny] = dis[p.first][p.second] + 1;
que.push(make_pair(nx, ny));
vis[nx][ny] = true;
}
}
}
}

return dis[size - 1][size - 1] == 0x3f3f3f3f ? -1 : dis[size - 1][size - 1];
}
};


  



转载于:https://www.cnblogs.com/ZhaoxiCheung/p/leetcode-shortest-path-in-binary-matrix.html



友情链接: