Sokoban P67923

Sokoban is a popular computer game originally created in 1982 by Hiroyuki Imabayashi at the Japanese company Thinking Rabbit, Inc. “Sokoban” is Japanese for warehouse keeper.

[r]

The goal is to move the boxes to their correct destinations in a crowded warehouse. The drawback is that our friend is not strong enough to lift one box over another, nor to pull boxes. He can only push one box at a time; two boxes at once are already too heavy. Moreover, a passage is just as narrow as a box, so if a box is blocking a path, he cannot go around it by just squeezing himself through between the box and the wall; he will need to find a clear path to reach the other side. And, of course, our friend cannot climb over boxes, either. In order to win this game, a player has to guide the keeper to move through the labyrinth of walls and boxes and to push all the boxes to their intended target spots.

Sokoban maps with different levels of difficulty are available on the Internet. For instance, the above figure is given by the following map:

####
# .#
#  ###
#*@  #
#  $ #
#  ###
####

The meaning of each character is the following: ‘#’ denotes a wall, a space denotes an empty square, ‘.’ denotes an empty goal square, ‘$’ denotes a box on a non-goal square (yellow in the picture), ‘*’ denotes a box on a goal square (red in the picture), the “at symbol” denotes the keeper on a non-goal square, and ‘+’ denotes the keeper on a goal square.

On these maps, these are the actions that our little friend can perform:

• Move to an adjacent empty square. By “adjacent” we mean to the left, right, up, or down, but not diagonally. Each of these actions is called a “move".
• Push an adjacent box to an empty square. Each of these actions is called a “push”.

For instance, a way to solve with 8 pushes the previous puzzle is given in the following 9 diagrams (read them from left to right, and note that only pushes are shown; moves are not displayed). In fact, there is no way to solve this Sokoban map in less than 8 pushes.

####     ####     ####     ####     ####     ####     ####     ####     ####
# .#     # .#     # .#     # .#     # .#     # .#     # .#     # .#     # *#
#  ###   #$ ###   #$ ###   #$ ###   #$ ###   # ###   #  ###   # $###   # ###
#*  #   #+   #   #.   #   #.$  #   #.$ #   #* $ #   #*$ #   #*  #   #*   #
#  $ #   #  $ #   # $ #   #   #   #    #   #    #   #    #   #    #   #    #
#  ###   #  ###   #  ###   #  ###   #  ###   #  ###   #  ###   #  ###   #  ###
####     ####     ####     ####     ####     ####     ####     ####     #### 

Write a program that, given a number k and a Sokoban map (that may not be solvable), indicates if it is possible or not to solve the game with k or less pushes. (The number of moves is not taken into account.)

Input

Input consists of several cases. Every case begins with a line with a number k, followed by a Sokoban map, followed by a blank line. You can assume 0 ≤ k ≤ 30, that the map fits in a 16 × 16 grid, that there are at most three boxes, and that there are as many boxes as targets. Lines may have different lengths.

Output

Print “YES” if the map can be solved with k or less pushes, and print “NO” otherwise.