https://discuss.leetcode.com/topic/122/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}
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}
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
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.
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.
