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}
Slider Maze


@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 example1 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 ret.add(0,dir[map[x1][y1][0]]); 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 Autogenerated 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(""); } }