Caterpillar in Panic - Githubissues

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

Task Description

We have an N x 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 x 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.

![figure]()

在 N x M 方格上有一條蛇，蛇身連續佔有 L 格。由於陌生的環境，進入慌張的蛇在方格亂竄，但牠始終無法越過邊界，亂竄活動將會持續到牠撞壁或者撞到自身。

pf 從觀察這條蛇的移動方式，得到以下資訊：

每一次完整的移動，將會先從蛇尾蜷曲，再將蛇頭往前伸。
蛇只能移動到相鄰的四格，假設蛇頭位在 (SX, SY)：
- 當移動方向 D = 0 時，蛇頭將會移動到 (SX+1, SY)
- 當移動方向 D = 1 時，蛇頭將會移動到 (SX-1, SY)
- 當移動方向 D = 2 時，蛇頭將會移動到 (SX, SY+1)
- 當移動方向 D = 3 時，蛇頭將會移動到 (SX, SY-1)

亂竄結束的瞬間帶來的衝擊，使得蛇身所在的位置無法復原。幸運地是，pf 只用紙筆記錄所有移動方向，現在請你復原最後一刻的蛇身所在的情況。

Input

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.

只有一組測資。

第一行有兩個整數 N, M，表示地圖長寬。第二行會有四個整數 SX, SY, EX, EY，表示蛇頭和蛇尾所在的格子座標，測試資料保證蛇一定平行兩軸。第三行有一個整數 Q，表示操作次數，接下來會有 Q 個整數 D，表示蛇每一時刻移動的方向。

0 < N, M <= 1000
0 <= SX, EX < N
0 <= SY, EY < M
0 <= Q <= 100000
D \in {0, 1, 2, 3}

Output

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

輸出 N 行，每一行上有 M 個 0/1 字元。第 i 行上的第 j 個字元，若蛇身在此位置上輸出 1，反之，輸出 1。

Sample Input 1

4 5
1 1 1 4
0

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

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

Sample Output 4

Sample Input 5

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

Sample Output 5

pangfengliu / programmingtasks

Caterpillar in Panic #330