You've successfully subscribed to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

1091. 二进制矩阵中的最短路径 - Shortest Path in Binary Matrix

【BFS】

• 相邻单元格 C_iC_{i+1} 在八个方向之一上连通（此时，C_iC_{i+1} 不同且共享边或角）
• C_1 位于 (0, 0)（即，值为 grid[0][0]
• C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）
• 如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0
返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。

Example:

1. 1 <= grid.length == grid[0].length <= 100
2. grid[i][j] 为 0 或 1

Solution 【BFS】

class Solution {
private boolean[][] map;
private boolean[][] isVisited;
private Node destNode;
public int shortestPathBinaryMatrix(int[][] grid) {
if (grid[0][0] == 1) return -1;
parse(grid);  // 为四周包裹障碍物
int row = map.length;
int col = map[0].length;

// System.out.println("=============TEST MAP================");
// for(int i = 0; i < row; i++) {
//     for (int j = 0; j < col; j++) {
//         System.out.print( (map[i][j] ? 0 : 1) + " ");
//     }
//     System.out.println();
// }
// System.out.println("=============TEST MAP================");

isVisited = new boolean[row][col];
destNode = new Node(row-2, col-2);
isVisited[1][1] = true;
int res= bfs(1, 1);
//
return res;
}

private int bfs(int iniX, int iniY) {
Node start = new Node(iniX, iniY);
start.setMove(1);
queue.offer(start);

while (!queue.isEmpty()) {
Node cur = queue.poll();
// System.out.println("At (" + cur.x + ", " + cur.y + ")");
if (cur.equals(destNode)) {
return cur.move;
}
int nextMove = cur.move + 1;
for (Node neighbor : getNeighbors(cur)) {
neighbor.setMove(nextMove);
queue.offer(neighbor);
isVisited[neighbor.x][neighbor.y] = true;
}
}
return -1;
}

private Iterable<Node> getNeighbors(Node node) {
Stack<Node> stack = new Stack<>();
short x = node.x;
short y = node.y;
if (map[x-1][y-1] && !isVisited[x-1][y-1]) {
stack.push(new Node(x-1, y-1));
}
if (map[x-1][y] && !isVisited[x-1][y]) {
stack.push(new Node(x-1, y));
}
if (map[x-1][y+1] && !isVisited[x-1][y+1]) {
stack.push(new Node(x-1, y+1));
}
if (map[x][y-1] && !isVisited[x][y-1]) {
stack.push(new Node(x, y-1));
}
if (map[x][y+1] && !isVisited[x][y+1]) {
stack.push(new Node(x, y+1));
}
if (map[x+1][y-1] && !isVisited[x+1][y-1]) {
stack.push(new Node(x+1, y-1));
}
if (map[x+1][y] && !isVisited[x+1][y]) {
stack.push(new Node(x+1, y));
}
if (map[x+1][y+1] && !isVisited[x+1][y+1]) {
stack.push(new Node(x+1, y+1));
}

//  System.out.println("number of neighbors:" + stack.size());
return stack;
}

private class Node{
short x;
short y;
short move;

public Node(int x, int y) {
this.x = (short)(x);
this.y = (short)(y);
}

public short getMove() {
return move;
}

public void setMove(int move) {
this.move = (short)(move);
}

public boolean equals(Node that) {
return this.x == that.x && this.y == that.y;
}
}

private void parse(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
map = new boolean[row + 2][col + 2];
for (int i = 0; i < col + 2; i++) {
map[0][i] = false;
map[row+1][i] = false;
}
for (int i = 0; i < row; i++) {
map[i+1][0] = false;
map[i+1][col+1] = false;
for (int j = 0; j < col; j++)
map[i+1][j+1] = grid[i][j] == 0;
}

}
}


Solution

class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
if(grid[row-1][col-1] == 1 || grid[0][0] == 1)
return -1;
return bfs(grid);
}
int bfs(int[][] grid) {
boolean[][] visit = new boolean[grid.length][grid[0].length];
Node node = new Node(0,0,1);
visit[0][0] = true;
queue.push(node);
int x[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int y[] = {-1, 0, 1, 1, 1, 0, -1, -1};
while(!queue.isEmpty()){
Node root = queue.removeFirst();
int val = root.value;
if(root.x == grid.length - 1 && root.y == grid[0].length - 1) {
return root.value;
}
for(int i = 0; i < x.length; i++) {
int row = root.x + x[i];
int col = root.y + y[i];
if(row >=0 && col >=0 && row < grid.length && col < grid[0].length && grid[row][col] == 0 && !visit[row][col]){
visit[row][col] = true;
}
}
}
return -1;
}
}
class Node{
int x;
int y;
int value;
public Node(int x, int y, int value){
this.x = x;
this.y = y;
this.value = value;
}
}