Sokoban#3111
Soko-ban is a Japanese word for a warehouse worker, and the name of a classic computer game created in the 1980s. It is a single-player game with the following premise: a worker is in an enclosed warehouse with one or more boxes. The goal is to move those boxes to a set of target locations, with the number of target locations equal to the number of boxes. The player indicates a direction of motion for the worker using the arrow keys (up, down, left, right), according to the following rules:
If the indicated direction of motion for the worker leads to an empty location (i.e., one that does not have a box or wall), the worker advances by one step in that direction.
If the indicated direction of motion would cause the worker to move into a box, and the location on the other side of the box is empty, then both the worker and the box move one spot in that direction (i.e., the worker pushes the box).
If the indicated direction of motion would cause the worker to move into a wall, or to move into a box that has another box or a wall on its opposite side, no motion takes place for that keystroke.
The goal is to have all boxes simultaneously placed on the target locations. In that case, the player is successful (and, as a formality, all further keystrokes are ignored).
The game has been studied by computer scientists (one graduate student wrote a whole Ph.D. dissertation about the analysis of sokoban). Unfortunately, finding a solution is generally very difficult, as the problem is both NP-hard and PSPACE-complete. Therefore, your task is simpler: to simulate the progress of a game based on a player's sequence of keystrokes. For the purposes of input and output, we describe the state of a game using the following symbols:
For example, the initial configuration diagrammed at the beginning of this problem appears below as the first input case.
Each game begins with a line containing integers and , where 4 \le R \le 15 is the number of rows, and 4 \le C \le 15 is the number of columns. Next, there are lines representing the rows from top to bottom, each line having exactly characters, from left to right. Finally, there is a line containing at most characters, describing the player's sequence of keystrokes, using the symbols , , , and for up, down, left, and right, respectively. You must read the entire sequence, even if a game may be completed before the sequence ends. The dataset ends with the line .
We guarantee that each game has exactly one worker, an equal number of boxes and target locations, at least one initially misplaced box, and an outermost boundary consisting entirely of walls.
For each game, first output a line indicating the game number, beginning at , and either the word complete or incomplete, indicating whether or not the player successfully completed that game. Then output a representation of the final board configuration.
Example 1