题目

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:

  1. Input: [[0,1],[1,0]]
  3. Output: 2

Example 2:

  1. Input: [[0,0,0],[1,1,0],[1,1,0]]
  3. Output: 4

Note:

  1. 1 <= grid.length == grid[0].length <= 100
  2. grid[r][c] is 0 or 1

题意

给定一个矩阵，其中值为1的格子不能走，为0的格子可以走。从每个格子出发有8个方向可走。求从左上到右下的最短路径。

思路

每条边的权值都为1，直接用BFS搜索最短路。

代码实现

Java

  1. class Solution {
  2.     public int shortestPathBinaryMatrix(int[][] grid) {
  3.         if (grid[0][0] == 1) return -1;
  5.         int steps = 0;
  6.         int n = grid.length;
  7.         Queue<int[]> q = new ArrayDeque<>();
  8.         boolean[][] visited = new boolean[n][n];
  9.         q.offer(new int[]{0, 0});
  10.         visited[0][0] = true;
  11.         while (!q.isEmpty()) {
  12.             int size = q.size();
  13.             steps++;
  14.             while (size > 0) {
  15.                 int[] cur = q.poll();
  16.                 int i = cur[0], j = cur[1];
  17.                 if (i == n - 1 && j == n - 1) {
  18.                     return steps;
  19.                 }
  20.                 for (int x = -1; x <= 1; x++) {
  21.                     for (int y = -1; y <= 1; y++) {
  22.                         if (x != 0 || y != 0) {
  23.                             int nextI = i + x, nextJ = j + y;
  24.                             if (isValid(nextI, nextJ, n) && !visited[nextI][nextJ] && grid[nextI][nextJ] == 0) {
  25.                                 visited[nextI][nextJ] = true;
  26.                                 q.offer(new int[]{nextI, nextJ});
  27.                             }
  28.                         }
  29.                     }
  30.                 }
  31.                 size--;
  32.             }
  33.         }
  34.         return -1;
  35.     }
  37.     private boolean isValid(int i, int j,int n){
  38.         return i < n && i >= 0 && j < n && j >= 0;
  39.     }
  40. }