50044. Caterpillar in Panic

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

Write a program to simulate a caterpillar moving on a grid.

Task Description

Read problems statements in 中文

We have an $N \times M$ grid $G$ of squares with a caterpillar in it. We use an $N$ by $M$ array to indicate the positions of the caterpillar. The row index is from $0$ to $N -1$, and the column index is from $0$ to $M - 1$. If an array cell is $1$ then it is a part of the caterpillar, and if the the cell is $0$ then it is a space. A caterpillar is a sequence of $L$ adjacent 1's on the grid, where two cells are adjacent if either their row or column indices differ by exactly $1$. A caterpillar has head (at the starting position of the adjacent 1's), and a tail (at the ending position of the adjacent 1's).

The caterpillar moves on the grid as follows. The caterpillar can either move east, west, south, or north, if the corresponding cell in that direction is a space, or the tail of the caterpillar. Note that a space is within the grid.

The caterpillar moves according to a sequence of directions, where $D_i$ is the $i$-th direction. Assume that the head is located at $(x, y)$, then the caterpillar moves as follows.

  • If $D_i$ equals 0, the head of the caterpillar moves to $(x+1, y)$.
  • If $D_i$ equals 1, the head of the caterpillar moves to $(x-1, y)$.
  • If $D_i$ equals 2, the head of the caterpillar moves to $(x, y+1)$.
  • If $D_i$ equals 3, the head of the caterpillar moves to $(x, y-1)$.

Write a program to simulate a caterpillar movement on the grid. The program simulates the movement according to directions or until it violates the rules of movement. Finally, output the values of the $N \times M$ grid.

Hint

You can use three arrays to store the current status of the caterpillar. The first $N$ by $M$ array stores the status of grid $G$, and another two arrays of length $L$ for the current row and column indices of each part of the caterpillar.

Take sample input $1$ for example. The data structure is shown in the figure below.

p10135. sample input 1 with $D = 0$
p10135. data structure
p10135. data structure after $D = 0$
p10135. grid $G$ after $D = 0$

Input Format

There is one test case.

The first line contains two integers $N, M$, representing the height and width of grids. The second line contains four integers $SX, SY, EX, EY$, representing the position of head and tail. The test set guarantee the snake parallel one axis. The third line contains an integer $Q$, representing the the number of directions. The following line contains $Q$ integers $D$, representing the direction of movement each time.

  • $0 \lt N, M \le 1000$
  • $0 \le SX, EX \lt N$
  • $0 \le SY, EY \lt M$
  • $0 \le Q \le 1000000$
  • $D \in \lbrace 0, 1, 2, 3\rbrace $

Output Format

Output file contains $N$ lines. Each line contains $M$ 0/1 integers. If the square belongs the caterpillar parts, output 1. Otherwise, output 0.

Sample Input 1

4 5
1 1 1 4
0

Sample Output 1

00000
01111
00000
00000

Sample Input 2

4 5
1 1 1 4
3
0 0 2

Sample Output 2

00000
01000
01000
01100

Sample Input 3

4 5
1 1 1 4
5
3 3 3 3 3

Sample Output 3

00000
11110
00000
00000

Sample Input 4

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

Sample Output 4

00000000
00000000
00000000
00000000
00000000
01110000
11010000
00110000

Sample Input 5

9 8
8 1 0 1
8
2 2 1 1 3 3 0 3

Sample Output 5

00000000
00000000
00000000
00000000
00000000
01000000
01110000
01010000
01110000

Discussion