LeetCode link

first thought

  • the same as maze II, using BFS.
  • need to record the path, and update the path at proper time.
  • there’s no need to iterate when the ball reach the hole.

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
public class Solution {
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        Queue<Point> queue = new LinkedList<>();
        int row = maze.length;
        int col = maze[0].length;
        Point[][] points = new Point[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                Point point = new Point(i, j);
                points[i][j] = point;
                if (i == hole[0] && j == hole[1]) {
                    point.path = "impossible";
                }
            }
        }
        int[] dirX = {0, -1, 1, 0}; // d, l, r, u
        int[] dirY = {1, 0, 0, -1};
        String[] dir = {"d", "l", "r", "u"};
        Point startPoint = points[ball[0]][ball[1]];
        startPoint.dis = 0;
        queue.add(startPoint);
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = point.x;
                int y = point.y;
                int dis = point.dis;
                String path = point.path;
                boolean inHole = false;
                while (x >= 0 && x < row && y >= 0 && y < col && maze[x][y] == 0) {
                    x += dirX[i];
                    y += dirY[i];
                    dis++;
                    if (x == hole[0] && y == hole[1]) {
                        inHole = true;
                        break;
                    }
                }
                if (!inHole) {
                    x -= dirX[i];
                    y -= dirY[i];
                    dis--;
                }
                Point newPoint = points[x][y];
                if (newPoint.dis > dis) {
                    newPoint.dis = dis;
                    newPoint.path = String.join("", point.path, dir[i]);
                    if (!inHole) {
                        queue.add(newPoint);
                    }
                } else if (newPoint.dis == dis) {
                    boolean updated = false;
                    String newPath = String.join("", point.path, dir[i]);
                    for (int k = 0; k < newPoint.path.length() && k < newPath.length(); k++) {
                        if (newPoint.path.charAt(k) > newPath.charAt(k)) {
                            updated = true;
                            newPoint.path = newPath;
                            break;
                        }
                    }
                    if (!updated && newPoint.path.length() > newPath.length()) {
                        newPoint.path = newPath;
                    }
                }
            }
        }
        return points[hole[0]][hole[1]].path;
    }
}
class Point {
    int x;
    int y;
    String path;
    int dis;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
        this.path = "";
        this.dis = Integer.MAX_VALUE;
    }
}

problem

wrong answer

reason

there’s one mistake in checking the order of paths.

modification

1
2
3
4
5
if (newPoint.path.charAt(k) > newPath.charAt(k)) {
    updated = true;
    newPoint.path = newPath;
    break;
}

change to

1
2
3
4
5
6
7
8
9
10
char c1 = newPoint.path.charAt(k);
char c2 = newPath.charAt(k);
if (c1 < c2) {
    updated = true;
    break;
} else if (newPoint.path.charAt(k) > newPath.charAt(k)) {
    updated = true;
    newPoint.path = newPath;
    break;
}

problem

wrong answer

input:
[[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]]
[4,3]
[0,1]

Your answer
“lu”

Expected answer
“lul”

reason

  • dirX, dirY are wrong.
  • there’s a method in String to compare two strings.

modification

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
public class Solution {
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        Queue<Point> queue = new LinkedList<>();
        int row = maze.length;
        int col = maze[0].length;
        Point[][] points = new Point[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                Point point = new Point(i, j);
                points[i][j] = point;
                if (i == hole[0] && j == hole[1]) {
                    point.path = "impossible";
                }
            }
        }
        int[] dirX = {1, 0, 0, -1}; // d, l, r, u
        int[] dirY = {0, -1, 1, 0};
        String[] dir = {"d", "l", "r", "u"};
        Point startPoint = points[ball[0]][ball[1]];
        startPoint.dis = 0;
        queue.add(startPoint);
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = point.x;
                int y = point.y;
                int dis = point.dis;
                boolean inHole = false;
                while (x >= 0 && x < row && y >= 0 && y < col && maze[x][y] == 0) {
                    x += dirX[i];
                    y += dirY[i];
                    dis++;
                    if (x == hole[0] && y == hole[1]) {
                        inHole = true;
                        break;
                    }
                }
                if (!inHole) {
                    x -= dirX[i];
                    y -= dirY[i];
                    dis--;
                }
                Point newPoint = points[x][y];
                if (newPoint.dis > dis) {
                    newPoint.dis = dis;
                    newPoint.path = String.join("", point.path, dir[i]);
                    if (!inHole) {
                        queue.add(newPoint);
                    }
                } else if (newPoint.dis == dis) {
                    String newPath = String.join("", point.path, dir[i]);
                    if (newPoint.path.compareTo(newPath) > 0) {
                        newPoint.path = newPath;
                    }
                }
            }
        }
        return points[hole[0]][hole[1]].path;
    }
}
class Point {
    int x;
    int y;
    String path;
    int dis;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
        this.path = "";
        this.dis = Integer.MAX_VALUE;
    }
}

problem

still wrong answer…

reason

when newPoint.dis == dis, it should re-put the point to the queue because although the dis is the same, the path is updated.

modification

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class Solution {
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        Queue<Point> queue = new LinkedList<>();
        int row = maze.length;
        int col = maze[0].length;
        Point[][] points = new Point[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                Point point = new Point(i, j);
                points[i][j] = point;
                if (i == hole[0] && j == hole[1]) {
                    point.path = "impossible";
                }
            }
        }
        int[] dirX = {1, 0, 0, -1}; // d, l, r, u
        int[] dirY = {0, -1, 1, 0};
        String[] dir = {"d", "l", "r", "u"};
        Point startPoint = points[ball[0]][ball[1]];
        startPoint.dis = 0;
        queue.add(startPoint);
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = point.x;
                int y = point.y;
                int dis = point.dis;
                boolean inHole = false;
                while (x >= 0 && x < row && y >= 0 && y < col && maze[x][y] == 0) {
                    x += dirX[i];
                    y += dirY[i];
                    dis++;
                    if (x == hole[0] && y == hole[1]) {
                        inHole = true;
                        break;
                    }
                }
                if (!inHole) {
                    x -= dirX[i];
                    y -= dirY[i];
                    dis--;
                }
                Point newPoint = points[x][y];
                String newPath = String.join("", point.path, dir[i]);
                if (newPoint.dis > dis || (newPoint.dis == dis && newPoint.path.compareTo(newPath) > 0)) {
                    newPoint.dis = dis;
                    newPoint.path = String.join("", point.path, dir[i]);
                    if (!inHole) {
                        queue.add(newPoint);
                    }
                }
            }
        }
        return points[hole[0]][hole[1]].path;
    }
}
class Point {
    int x;
    int y;
    String path;
    int dis;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
        this.path = "";
        this.dis = Integer.MAX_VALUE;
    }
}