1091. 二进制矩阵中的最短路径

题目：给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

路径途经的所有单元格的值都是 0 。 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。 畅通路径的长度 是该路径途经的单元格总数。

解题思路：

  1. 从左上角开始，将起始位置加入到队列中，并标记为已访问。
  2. 从队列中依次取出位置，探索其周围八个方向的相邻位置，如果相邻位置可通过且未被访问，则将其加入队列，并标记为已访问，并将其路径长度加1。
  3. 不断重复这个过程，直到达到右下角位置或者队列为空。
  4. 如果成功到达右下角，则返回路径长度；否则返回-1表示无法到达。
  type coordinate struct {
  	x, y int
  }

func shortestPathBinaryMatrix(grid [][]int) int {
	  n := len(grid)
	  if n == 0 {
	  	return -1
	  }
      
	  m := len(grid[0])
	  if grid[0][0] == 1 || grid[n-1][m-1] == 1 {
	  	return -1
	  }
      
	  queue := list.List{}
	  queue.PushBack(coordinate{
	  	x: 0,
	  	y: 0,
	  })
	  var visitedMap = make(map[coordinate]bool)
	  visitedMap[coordinate{
	  	x: 0,
	  	y: 0,
	  }] = true
      
	  directions := [][]int{{0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}}
      
	  var steps = 1
	  for queue.Len() > 0 {
	  	size := queue.Len()
	  	for i := 0; i < size; i++ {
	  		curr := queue.Remove(queue.Front()).(coordinate)
	  		if curr.x == m-1 && curr.y == n-1 {
	  			return steps
	  		}
	  		for _, dir := range directions {
	  			next := coordinate{
	  				x: curr.x + dir[0],
	  				y: curr.y + dir[1],
	  			}
	  			// 有效&&未访问
	  			if isValid(next, grid) && !visitedMap[next] {
	  				queue.PushBack(next)
	  				visitedMap[next] = true
	  			}
	  		}
	  	}
	  	steps++
	  }
	  return -1
}

  func isValid(c coordinate, grid [][]int) bool {
  	n := len(grid)
  	return c.x >= 0 && c.x < n && c.y >= 0 && c.y < n && grid[c.x][c.y] == 0
  }