# Slider Maze

• Slider Maze
There is a game called slider maze, you give a direction of the ball in the first place but the ball cannot be stopped until it hits a wall or the boundary. The question is to output the move sequence of the ball that is the shortest one. The input will be a maze, an initial position and an end position. As an example in the link above, the output should be （’Down’,’Right’,’Down’,’Right’,’Down’,’Left’,’Down’,’Left’,’Up’,’Left’) you can represent the direction as {0,-1},{0,1}{-1,0},{1,0}

• ZackerZ, I coudn't open your example, but did I try the game. Do you mean by shortest path, the shortest path between avatar and the food?
Can we apply Dijkstra for this?

• @elmirap Yes, It is the shortest path from the start point of the ball to the end point which you can think of it like an exit. I think it can be solved by BFS but the implementation is a little bit tricky since you need to find the next stop position of the ball.

• @ZhackerZ With BFS (not Dijkstra because of the higher time complexity of the last) we need to expand each time by one, as it was in original BFS, but for some nodes (which are not stops) we will expand only in one direction.
For example

1 1 1 S 1 1
1 0 0 0 1 1
1 0 0 0 1 1
1 F 1 1 11
1 - wall
S - start
F - food
we add (1,3) to the BFS queue, but (1,3) is not end node ( the avatar can not stop there), we will mark in some way this fact that (1,3) is not a stop and its direction. Next time we expand the BFS tree from (1,3), we will expand it only in direction Down.

• My BFS implementation:

``````public class SliderMaze {

public List<String> findShortestPathBFS(int[][] maze, int x0, int y0, int x1, int y1) {
List<String> ret = new ArrayList<String>();
if (maze == null || maze.length == 0) return ret;
int[][] nb = {{0,0},{0,1},{1,0},{0,-1},{-1,0}};
String[] dir = {"","Right","Down","Left","Up"};
int cols = maze.length;
int rows = maze[0].length;
// This map stores the direction and the previous location (x,y).
// Also, serves as the memory to mark visited locations.
int[][][] map = new int[cols][rows][3]; // map[cols][rows][ dir, x, y]
Stack<Integer> xx = new Stack<Integer>();
Stack<Integer> yy = new Stack<Integer>();
Stack<Integer> temp_x = new Stack<Integer>();
Stack<Integer> temp_y = new Stack<Integer>();
xx.push(x0); yy.push(y0);
map[x0][y0][0] = 5; // Direction = 5 means the starting point;
while (! xx.isEmpty()) {
int x = xx.pop(), y = yy.pop();
if (x==x1 && y==y1) { // Goal!
while( map[x1][y1][0] != 5) { // tracing back the path
x = map[x1][y1][1];	y = map[x1][y1][2];
x1 = x;	y1 = y;
}
return ret; // return the path
} else {
for (int i=1; i<=4; i++) { // try 4 directions
int dx = nb[i][0], dy = nb[i][1];
int x2 = x, y2 = y;
// rolling the ball until stopped by a wall
while (x2+dx >=0 && y2+dy >=0 && x2+dx < cols && y2+dy < rows
&& maze[x2+dx][y2+dy] == 0 ) {
x2+=dx; y2+=dy;
}
// check whether the stopping location has been visited
if (map[x2][y2][0] == 0 && !(x==x2 && y==y2) ) {
map[x2][y2][0] = i; // store the direction
map[x2][y2][1] = x; // store the previous location
map[x2][y2][2] = y;
temp_x.push(x2); temp_y.push(y2);
String move =String.format("from (%d, %d) to (%d %d)", x,y,x2,y2);
System.out.println(  move + " "+ dir[i] );
}
}
}
if (xx.isEmpty()) {
xx = temp_x; yy = temp_y;
temp_x = new Stack<Integer>();
temp_y = new Stack<Integer>();
}
}
// no path can reach the goal, return an empty list
return ret;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] maze = {{0,0,0,1,0},{0,0,1,0,0},{0,0,0,0,1},{1,0,0,0,0}};
SliderMaze sol = new SliderMaze();
List<String> path = sol.findShortestPathBFS(maze, 0, 0, 3, 4);
for (String str: path) {
System.out.print(str+",");
}
System.out.println("");
}
}
``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.