題目
在一個 N × N 的方形網格中，每個單元格有兩種狀態：空（0）或者阻塞（1）。
一條從左上角到右下角、長度為 k 的暢通路徑，由滿足下述條件的單元格 C_1, C_2, ..., C_k 組成：
相鄰單元格 C_i 和 C_{i+1} 在八個方向之一上連通（此時，C_i 和 C_{i+1} 不同且共享邊或角）
C_1 位於 (0, 0)（即，值為 grid[0][0]）
C_k 位於 (N-1, N-1)（即，值為 grid[N-1][N-1]）
如果 C_i 位於 (r, c)，則 grid[r][c] 為空（即，grid[r][c] == 0）
返回這條從左上角到右下角的最短暢通路徑的長度。如果不存在這樣的路徑，返回 -1 。
示例 1：輸入：[[0,1],[1,0]] 輸出：2
示例 2：輸入：[[0,0,0],[1,1,0],[1,1,0]] 輸出：4
提示：1 <= grid.length == grid[0].length <= 100
grid[i][j] 為 0 或 1
解題思路分析1、廣度優先搜尋；時間複雜度O(n^2)，空間複雜度O(n)
var dx = []int{-1, -1, -1, 0, 0, 1, 1, 1}var dy = []int{-1, 0, 1, -1, 1, -1, 0, 1}func shortestPathBinaryMatrix(grid [][]int) int { if grid[0][0] == 1 { return -1 } n, m := len(grid), len(grid[0]) if grid[n-1][m-1] == 1 { return -1 } if n == 1 && m == 1 { return 1 } visited := make(map[[2]int]bool) visited[[2]int{0, 0}] = true queue := make([][3]int, 0) queue = append(queue, [3]int{0, 0, 1}) for len(queue) > 0 { node := queue[0] queue = queue[1:] x := node[0] y := node[1] v := node[2] for i := 0; i < 8; i++ { newX := x + dx[i] newY := y + dy[i] if 0 <= newX && newX < n && 0 <= newY && newY < m && grid[newX][newY] == 0 && visited[[2]int{newX, newY}] == false { queue = append(queue, [3]int{newX, newY, v + 1}) visited[[2]int{newX, newY}] = true if newX == n-1 && newY == m-1 { return v + 1 } } } } return -1}2、廣度優先搜尋；時間複雜度O(n^2)，空間複雜度O(n)
var dx = []int{-1, -1, -1, 0, 0, 1, 1, 1}var dy = []int{-1, 0, 1, -1, 1, -1, 0, 1}func shortestPathBinaryMatrix(grid [][]int) int { if grid[0][0] == 1 { return -1 } n, m := len(grid), len(grid[0]) if grid[n-1][m-1] == 1 { return -1 } if n == 1 && m == 1{ return 1 } queue := make([]int, 0) queue = append(queue, 0) grid[0][0] = 1 for len(queue) > 0 { node := queue[0] queue = queue[1:] x := node / m y := node % m for i := 0; i < 8; i++ { newX := x + dx[i] newY := y + dy[i] if 0 <= newX && newX < n && 0 <= newY && newY < m && grid[newX][newY] == 0 { queue = append(queue, newX*m+newY) grid[newX][newY] = grid[x][y] + 1 if newX == n-1 && newY == m-1 { return grid[n-1][m-1] } } } } return -1}Medium題目，採用廣度優先搜尋解題