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];} };

　　

轉(zhuǎn)載于:https://www.cnblogs.com/ZhaoxiCheung/p/leetcode-shortest-path-in-binary-matrix.html

總結(jié)

以上是生活随笔為你收集整理的[LeetCode] 1091. Shortest Path in Binary Matrix的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。