LeetCode link

first thought

  • Using BFS
  • How to maintain the distance of each position. => Build a int[][] .
  • The first reach of destination may not be the best solution, but there’s no need to put destination to the queue(aka there’s no need to continue iterating from destination)

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class Solution {
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        Queue<Position> queue = new LinkedList<>();
        int row = maze.length;
        int col = maze[0].length;
        int[][] distance = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                distance[i][j] = Integer.MAX_VALUE;
            }
        }
        queue.add(new Position(start[0], start[1]));
        distance[start[0]][start[1]] = 0;
        int[] dirX = {-1, 0, 1, 0};
        int[] dirY = {0, 1, 0, -1};
        while (!queue.isEmpty()) {
            Position pos = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = pos.x;
                int y = pos.y;
                int dis = distance[x][y];
                while (x >= 0 && x < row && y >= 0 && y < col && maze[x][y] == 0) {
                    x += dirX[i];
                    y += dirY[i];
                    dis++;
                }
                x -= dirX[i];
                y -= dirY[i];
                dis--;
                if (distance[x][y] > dis) {
                    distance[x][y] = dis;
                    if (x != destination[0] || y != destination[1]) {
                        queue.add(new Position(x, y));
                    }
                }
            }
        }
        int result = distance[destination[0]][destination[1]];
        return result < Integer.MAX_VALUE ? result : -1;
    }
}
class Position {
    int x;
    int y;
    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}