题目
https://leetcode.com/problems/shortest-path-in-binary-matrix/
从方格的左上角走到右下角，请问最短路径是多少？
解题思路
第一反应是dp，感觉这要是不用dp还有天理？
但是 细想就发现，相比较于以前的dp的题目，原先的题目都限定了走路的方向要么向右，要么向下，而这个题目是八个方向都可以走，
有点难，但是一想就是很明显的 bfs啦。
代码
import java.util.LinkedList;
class Solution {
public static int shortestPathBinaryMatrix(int[][] grid) {
int v1 = grid.length;
int v2 = grid[0].length;
if (v1 == 1 && v2 == 1 && grid[0][0] == 0) {
return 1;
}
if (grid[0][0] > 0 || grid[v1 - 1][v2 - 1] > 0) {
return -1;
}
boolean[][] visit = new boolean[v1][v2]; //是否放进去过队列
int[][] dis = new int[v1][v2];
dis[0][0] = 1;
LinkedList<int[]> queue = new LinkedList<>();
queue.addLast(new int[]{0, 0});
visit[0][0] = true;
int[][] dirs = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
while (!queue.isEmpty()) {
int[] point = queue.pollFirst();
int i = point[0];
int j = point[1];
visit[i][j] = true;
for (int[] d : dirs) {
int nextI = i + d[0];
int nextJ = j + d[1];
//越界
if (nextI < 0 || nextI >= v1 || nextJ < 0 || nextJ >= v2) {
continue;
}
//如果是障碍，不处理
if (grid[nextI][nextJ] > 0) {
continue;
}
if (dis[nextI][nextJ] == 0 || dis[nextI][nextJ] > dis[i][j] + 1) {
dis[nextI][nextJ] = dis[i][j] + 1;
}
//装到队列里
if (!visit[nextI][nextJ]) {
queue.addLast(new int[]{nextI, nextJ});
visit[nextI][nextJ] = true;
}
}
}
return dis[v1 - 1][v2 - 1] > 0 ? dis[v1 - 1][v2 - 1] : -1;
}
}
