Slider Maze


  • 0
    Z

    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}


  • 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?


  • 0
    Z

    @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.


  • 1

    @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.


  • 0

    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 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("");
    	}
    }
    

  • 0
    This post is deleted!

Log in to reply
 

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