Indian Computing Olympiad

Heaps→Sokoban

Given a square grid with some blocked positions in which there is a Sokoban player (S) and a block (B). The player S has to move the block B to a target square T. Assume that the grid is at most 20×20.

Here is an example maze

           ###########         S -- You
           #T##......#         B -- Box
           #.#.#..####         # -- Blocked square
           #....B....#         T -- Target
           #.######..#         . -- Empty cell
           #.....S...#
           ###########
      

The only way to move the block is to push it. So, there are two types of moves for S:

• Walk east/west/north/south without pushing : Represent as e/w/n/s
• Push east/west/north/south: Represent as E/W/N/S

To push, S must be oriented correctly with respect to B. Thus, to push B west, S must be one square to the east of B. A push moves both S and B one step in the direction of the push.

Find a way to move B to T that minimizes the number of pushes. If two solutions have the same number of pushes, find the one with the minimum number of walks.

For example, here is a solution for the grid above:

	eennwwWWWWeeeeeesswwwwwwwnnNN
      

Solution

---