50121. Push Stones

I'm a slow walker, but I never walk backwards.

This is a game about a stone pushing.

Task Description

We have an $N$ by $M$ map with one player and $W$ stones. The vertical index is from $0$ to $N-1$, and the horizontal index is from $0$ to $M-1$.

The player will act according to the instructions. Each instruction is a number from $0$ to $4$. Let the current position of the player be $(x, y)$. The following is the action the play should perform when he receives that instruction.

  • If the instruction is $0$, output the current map information.
  • If the instruction is $1$, the person walks from $(x, y)$ to $(x + 1, y)$.
  • If the instruction is $2$, the person walks from $(x, y)$ to $(x, y + 1)$.
  • If the instruction is $3$, the person walks from $(x, y)$ to $(x - 1, y)$.
  • If the instruction is $4$, the person walks from $(x, y)$ to $(x, y - 1)$.

The coordinate system is defined as follows:

Coordinate

There are also stones in the map. Every stone is in its own cell and has a weight. A player also has an amount of energy. When the player moves into an empty cell, his energy will not change. However, if the player moves and encounters a stone, he needs to push it, along with all the stones behind it, all the way to the first empty cell in that direction. If the player’s energy is at least the sum of the weights of the stones he has to push, then he can push them. That is, he and the stones he pushed will move one cell in that direction. After he pushes the stones, his energy will decrease by the sum of the weights of the stone he pushed. On the other hand, if the player’s energy is less than the sum of the weights of the stone he wants to push, then he cannot push them, and he will stay in same cell. Also note that the player will ignore any instruction that causes the person or any stone to be out of the map.

Write a program to simulate this game, and output the map information when given instruction $0$.

Take sample input 3 for example. The figure is shown below.

Sample input 3

Subtask

  • 10 points: There are no stones in the map.
  • 20 points: There is only one stone in the map.
  • 70 points: There could be multiple stones in the map.

Input Format

The input contains only one test case. The first line contains two integers $N$ and $M$, which are the vertical and horizontal size of the map. The second line contains three integers, the player’s row index, column index, and energy. The third line contains one integer $O$ representing the number of stones. Each of the following $O$ lines contains three integers for row index, column index, and the weight of stones. The last line contains the instructions. You need to process them until the end of file. The number of instructions is at least one.

  • $0 \lt N, M \leq 500$
  • $0 \leq O \lt N \times M$

Output Format

Print the current map information if the instruction is $0$. This information includes the person’s energy and the weight of stones. The rest of cells are zero.

Note that there is no space at the end of line.

Sample Input 1

3 3
0 0 5
0
0 1 0 4 0 1 2 1 2 1 2 0

Sample Output 1

5 0 0
0 0 0
0 0 0
0 5 0
0 0 0
0 0 0
0 5 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 5

Sample Input 2

4 4
1 0 7
1
1 1 2
0 1 1 1 0 4 1 2 2 2 0

Sample Output 2

0 0 0 0
7 2 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 3 2
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 2
0 0 0 0

Sample Input 3

4 7
1 0 9
6
2 0 1
2 1 1
2 2 1
0 2 1
1 2 1
2 4 2
4 4 2 2 1 1 1 4 0

Sample Output 3

0 0 1 0 0 0 0
0 0 1 0 0 0 0
0 0 2 1 1 2 0
1 0 0 0 0 0 0

Discussion