This page looks best with JavaScript enabled

Leetcode 1091 Shortest Path in Binary Matrix

Problem

https://leetcode.com/problems/shortest-path-in-binary-matrix/

題目解釋

  • 0 代表可走, 1 不可
  • 從左上角走到右下,可走任意直橫斜,回傳最短路線的 0 的數量,若無法有路線回傳 -1

陣列題目限制為方陣,但下方實作直接當作矩陣

My Solution

test case

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from typing import List

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        pass

inpu = ([
        [0, 1],
        [1, 0],
        [1, 0], ],
        [
        [0, 0, 0],
        [1, 1, 0],
        [1, 1, 0], ],
        [
        [0, 1, 1, 0, 1, 1],
        [0, 1, 0, 1, 0, 1],
        [1, 0, 1, 1, 0, 1],
        [1, 1, 1, 1, 1, 0], ],
        [
        [0, 0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0, 1],
        [0, 0, 1, 0, 1, 0, 0],
        [0, 0, 0, 1, 1, 1, 0],
        [1, 0, 0, 1, 1, 0, 0],
        [1, 1, 1, 1, 1, 0, 1],
        [0, 0, 1, 0, 0, 0, 0], ],
        )
print([SolutionDFS().shortestPathBinaryMatrix(i) for i in inpu])

DFS

( https://leetcode.com/problems/shortest-path-in-binary-matrix/discuss/312922/JavaPython-3-concise-BFS-and-DFS-codes-wo-changing-input.)

  • 走過的點可以重複走
  • 可被走的條件為步數當前位置步數差大於 1

很慢

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 3700 ms, 5%
class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] or grid[-1][-1]:
            return -1
        rows, cols = len(grid), len(grid[0])
        d = {(0, 0): 1}

        def dfs(r=0, c=0):
            nxt = [(i, j) for i in range(r - 1, r + 2)
                   for j in range(c - 1, c + 2)]
            for nr, nc in nxt:
                cen = d.get((r, c), float('inf'))
                adj = d.get((nr, nc), float('inf'))
                if nr in range(rows) and nc in range(cols) and not grid[nr][nc]:
                    if abs(cen - adj) > 1:
                        if cen - adj > 1:
                            d[(r, c)] = adj + 1
                        else:
                            d[(nr, nc)] = cen + 1
                        dfs(nr, nc)
        dfs()
        last = d.get((rows - 1, cols - 1), float('inf'))
        return last if last <= rows * cols else -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 2600 ms, 5%
class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] or grid[-1][-1]:
            return -1
        rows, cols = len(grid), len(grid[0])
        d = [[float('inf') for c in range(cols)] for r in range(rows)]
        d[0][0] = 1

        def dfs(r=0, c=0):
            nxt = [(i, j) for i in range(r - 1, r + 2)
                   for j in range(c - 1, c + 2)]
            for nr, nc in nxt:
                if nr in range(rows) and nc in range(cols) and not grid[nr][nc]:
                    cen = d[r][c]
                    adj = d[nr][nc]
                    if abs(cen - adj) > 1:
                        if cen - adj > 1:
                            d[r][c] = adj + 1
                        else:
                            d[nr][nc] = cen + 1
                        dfs(nr, nc)
        dfs()
        last = d[rows - 1][cols - 1]
        return last if last <= rows * cols else -1

BFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# 770 ms, 40%
class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] or grid[-1][-1]:
            return -1
        grid[0][0] = 1  # mark walked
        rows, cols = len(grid), len(grid[0])
        q = [(0, 0, 1)]
        for r, c, d in q:  # current step: (r, c), distance: d
            if (r, c) == (rows-1, cols-1):
                return d
            nxt = [(i, j) for i in range(r - 1, r + 2)
                   for j in range(c - 1, c + 2)]
            for nr, nc in nxt:
                if 0 <= nr < rows and 0 <= nc < cols and not grid[nr][nc]:
                    grid[nr][nc] = 1  # mark walked
                    q += [(nr, nc, d+1)]
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
# 680 ms, 65%
class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] or grid[-1][-1]:
            return -1
        rows, cols = len(grid), len(grid[0])
        q, seen = [(0, 0, 1)], set([0])
        for r, c, d in q:
            if (r, c) == (rows-1, cols-1):
                return d
            for nr in [r-1, r, r+1]:
                for nc in [c-1, c, c+1]:
                    if 0 <= nr < rows and 0 <= nc < cols and not grid[nr][nc] and nr * cols + nc not in seen:
                        seen.add(nr * cols + nc)
                        q += [(nr, nc, d + 1)]
        return -1

DFS & BFS 比較

dfs

bfs

  • 優先走周圍的格子,步數少的會先走到,第一次走到終點的步數即是答案
  • 每個格子只要被走到一次即可,因為先走到的步數會小於等於較晚走到的步數

https://leetcode.com/problems/shortest-path-in-binary-matrix/discuss/313347/A*-search-in-Python