z-sokoban
Little Z loves playing logical games. At the moment he is playing Sokoban, one of his favourite.But he's stuck on some difficult levels, so he is asking you to help him to solve the puzzle.
Sokoban is a transport puzzle in which the player pushes the box around a maze (a warehouse), viewed from above,and tries to put it in designated location.The box cannot be pulled.The player can move only horizontally and vertically, but not diagonally.
In this simplified version of Sokoban, we have only one box that has to be moved to the final destination.
You will be given the plan of the warehouse, the player initial position, the position of the box and the final destination.
You have to return the minimum number of moves needed to push the box to the final location
The maze is surrounded with walls from all 4 sides.
The maze is given as a two-dimensional array of :
- walkable area is represented with '.'
- walls are represented with '#'
- the players initial position is given with 'P'
- the initial location of the box is given with 'B'
- and the final destination where you have to move the box is given with 'F'.
For example, in the maze bellow, you need 6 moves to solve the puzzle:
- push the box one cell up (1 move)
- move in the cell that is to the right of the box (2 moves)
- push the box three cells to the left (3 moves)
Sokoban is a transport puzzle in which the player pushes the box around a maze (a warehouse), viewed from above,and tries to put it in designated location.The box cannot be pulled.The player can move only horizontally and vertically, but not diagonally.
In this simplified version of Sokoban, we have only one box that has to be moved to the final destination.
You will be given the plan of the warehouse, the player initial position, the position of the box and the final destination.
You have to return the minimum number of moves needed to push the box to the final location
The maze is surrounded with walls from all 4 sides.
The maze is given as a two-dimensional array of :
- walkable area is represented with '.'
- walls are represented with '#'
- the players initial position is given with 'P'
- the initial location of the box is given with 'B'
- and the final destination where you have to move the box is given with 'F'.
For example, in the maze bellow, you need 6 moves to solve the puzzle:
- push the box one cell up (1 move)
- move in the cell that is to the right of the box (2 moves)
- push the box three cells to the left (3 moves)
####### ####### ####### ####### ####### ####### #######
#F....# #F..B.# #F..B.# #F..BP# #F.BP.# #FBP..# #BP...#
####B.# ####P.# ####.P# ####..# ####..# ####..# ####..#
#...P.# #.....# #.....# #.....# #.....# #.....# #.....#
####### ####### ####### ####### ####### ####### #######
Input In the first line will be the numbers N and M (1<=N,M<=30). Each of the next N lines will contain M characters, which represent the maze.All elements in the maze will consist of '#', '.', 'P', 'F', 'B'.There will be only one from each of 'P', 'F' and 'B'.
Output You should output the minimum number of player moves needed to push the box to the destination. If the box can not be pushed to the final destination, output "-1" without quotes.
Input
Output
5 7
#######
#F....#
####B.#
#...P.#
#######Output
6 Input
5 9
P........
...####..
....B.#..
.........
........F
Output25Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.