[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:
Input: [[0,1],[1,0]]
Output: 2

Example 2:
Input: [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

 

Note:

1 <= grid.length == grid[0].length <= 100

grid[r][c] is 0 or 1

思路

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

题解：bfs得到最短距离

 

static const auto io_sync_off = []() {// turn off syncstd::ios::sync_with_stdio(false);// untie in/out streamsstd::cin.tie(nullptr);return nullptr; }();class Solution { public:int shortestPathBinaryMatrix(vector<vector<int>>& 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<pair<int,int>>que;if (grid[0][0] == 0){que.push(make_pair(0, 0));dis[0][0] = 1;vis[0][0] = true;}while(!que.empty()){pair<int, int>p = 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

总结

以上是生活随笔为你收集整理的[LeetCode] 1091. Shortest Path in Binary Matrix的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。