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

问题1091 二进制矩阵中的最短路径 ★★☆☆☆

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

这个题目和问题542、问题994很类似，稍有区别就是这个题目是可以斜着遍历，即可以以相邻点做遍历，而不限于相邻边。简单来说就是从源点开始按宽度做扩散，每次处理一批距离源点相同宽度的0点，判断这些0点中是否已经扩散到了终点，如果是，返回depth长度。如果不是，则把下一宽度能扩散到的0点入队列。如果遍历结束都没有扩散到终点，则没有clear path，返回-1。

	private int[] dx = new int[] {-1, -1, -1, 0, 1, 1, 1, 0};
	private int[] dy = new int[] {-1, 0, 1, 1, 1, 0, -1, -1};

	public int shortestPathBinaryMatrix(int[][] grid) {
		int n = grid.length;

		if (grid[0][0] != 0 || grid[n-1][n-1] != 0) {
			return -1;
		}

		boolean[][] visited = new boolean[n][n];

		Queue<int[]> queue = new LinkedList<>();

		queue.add(new int[] {0, 0});
		visited[0][0] = true;
		int depth = 0;

		while (!queue.isEmpty()) {
			depth++;

			int size = queue.size();
			while (size-- > 0) {
				int[] cur = queue.poll();
				int row = cur[0], col = cur[1];

				if (row == n-1 && col == n-1) {
					return depth;
				}

				for (int k = 0; k < dx.length; k++) {
					int newRow = row + dx[k];
					int newCol = col + dy[k];

					if (newRow < 0 || newRow >= n || newCol < 0 || newCol >= n) {
						continue;
					}

					if (grid[newRow][newCol] == 0
						&& !visited[newRow][newCol]) {
						queue.add(new int[] {newRow, newCol});
						visited[newRow][newCol] = true;
					}
				}
			}
		}

		return -1;
	}

在 LeetCode 查看