day-102 二进制矩阵中的最短路径

思路
BFS

解题过程
从起点依次向八个方向尝试（之后也一样），如果某个位置在矩阵内且值为0且没有访问过，将其添加到一个队列中，依次类推，直到到达出口

Code

class Solution {public int shortestPathBinaryMatrix(int[][] grid) {int ans = 1;int nn = grid.length;int vis[][] = new int[nn][nn];vis[0][0] = 1;LinkedList<int[]> q = new LinkedList<>();if (grid[0][0] == 1)return -1;q.add(new int[] { 0, 0 });while (!q.isEmpty()) {int len = q.size();for (int i = 0; i < len; i++) {int arr[] = q.poll();int x = arr[0];int y = arr[1];if (x == nn - 1 && y == nn - 1)return ans;for (int m = x - 1; m <= x + 1; m++) {for (int n = y - 1; n <= y + 1; n++) {if (0 <= m && m < nn && 0 <= n && n < nn && vis[m][n] == 0&& grid[m][n] == 0) {grid[m][n] = 1;q.offer(new int[] { m, n });}}}}ans++;}return -1;}}作者：菜卷
链接：https://leetcode.cn/problems/shortest-path-in-binary-matrix/solutions/3034582/er-jin-zhi-ju-zhen-zhong-de-zui-duan-lu-xsg22/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。