# 499 The Maze III

There is a

**ball**in a maze with empty spaces and walls. The ball can go through empty spaces by rolling**up**(u),**down**(d),**left**(l) or**right**(r), but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction. There is also a**hole**in this maze. The ball will drop into the hole if it rolls on to the hole.Given the

**ball position**, the**hole position**and the**maze**, find out how the ball could drop into the hole by moving the**shortest distance**. The distance is defined by the number of**empty spaces**traveled by the ball from the start position (excluded) to the hole (included). Output the moving**directions**by using 'u', 'd', 'l' and 'r'. Since there could be several different shortest ways, you should output the**lexicographically smallest**way. If the ball cannot reach the hole, output "impossible".The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The ball and the hole coordinates are represented by row and column indexes.

**Example 1**

Input 1: a maze represented by a 2D array

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

Input 2:

ball coordinate (rowBall, colBall) = (4, 3)

Input 3:

hole coordinate (rowHole, colHole) = (0, 1)

Output:

"lul"

Explanation:

There are two shortest ways for the ball to drop into the hole.

The first way is left ->up -> left, represented by "lul".

The second way is up ->left, represented by 'ul'.

Both ways have shortest distance 6, but the first way is lexicographically smaller because 'l' <'u'. So the output is "lul".

**Example 2**

Input 1: a maze represented by a 2D array

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

Input 2: ball coordinate (rowBall, colBall) = (4, 3)

Input 3: hole coordinate (rowHole, colHole) = (3, 0)

Output: "impossible"

Explanation:

The ball cannot reach the hole.

**Note:**

- 1.There is only one ball and one hole in the maze.
- 2.Both the ball and hole exist on an empty space, and they will not be at the same position initially.
- 3.The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
- 4.The maze contains at least 2 empty spaces, and the width and the height of the maze won't exceed 30.

**(1) BFS:**

class Solution {

class Point {

int row, col, dist;

public Point(int row, int col, int dist) {

this.row = row;

this.col = col;

this.dist = dist;

}

}

public String findShortestWay(int[][] maze, int[] ball, int[] hole) {

if (maze == null || maze.length == 0) {

return "";

}

int m = maze.length, n = maze[0].length;

int[][] distance = new int[m][n];

for (int i = 0; i < m; i++) {

Arrays.fill(distance[i], Integer.MAX_VALUE);

}

distance[ball[0]][ball[1]] = 0;

int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

String[] ways = {"u", "d", "l", "r"};

Map<Integer, String> map = new HashMap<>();

Queue<Point> queue = new LinkedList<>();

queue.add(new Point(ball[0], ball[1], 0));

findShortestWayByBFS(maze, queue, map, distance, hole, ways, directions);

return map.containsKey(hole[0] * n + hole[1]) ? map.get(hole[0] * n + hole[1]) : "impossible";

}

public void findShortestWayByBFS(int[][] maze, Queue<Point> queue, Map<Integer, String> map, int[][] distance, int[] hole, String[] ways, int[][] directions) {

int n = maze[0].length;

while (!queue.isEmpty()) {

Point curPoint = queue.remove();

for (int i = 0; i < 4; i++) {

int row = curPoint.row, col = curPoint.col, dist = curPoint.dist;

String path = map.getOrDefault(row * n + col, "");

while (isValid(row, col, maze, hole)) {

row += directions[i][0];

col += directions[i][1];

++dist;

}

if (row != hole[0] || col != hole[1]) {

row -= directions[i][0];

col -= directions[i][1];

--dist;

}

path += ways[i];

if (dist < distance[row][col]) {

distance[row][col] = dist;

map.put(row * n + col, path);

queue.add(new Point(row, col, dist));

}

else if (dist == distance[row][col] && path.compareTo(map.getOrDefault(row * n + col, "")) < 0) {

map.put(row * n + col, path);

queue.add(new Point(row, col, dist));

}

}

}

}

public boolean isValid(int row, int col, int[][] maze, int[] hole) {

return row >= 0 && row < maze.length && col >= 0 && col < maze[0].length && maze[row][col] == 0 && (row != hole[0] || col != hole[1]);

}

}

BFS: 时间复杂度O(m * n * Max(m,n))，空间复杂度O(mn)

Last modified 3yr ago