Write a program to simulate a snake on a plane. The plane is a M by M (1 ≤ M ≤ 100) grid where (0, 0) is at the upper-left corner. Initially the snake is of length N (N ≥ 3) and facing east, and its head is locating at (x, y). That is, the snake occupied (x, y), (x - 1, y), ... (x - N + 1, y) grid points (N - 1 ≤ x < M). Now we give a sequence of commands to this snake so it moves around in this plane. If the command is 1, then the snake moves east. If the command is 2, then the snake moves south. If the command is 3, then the snake moves west. If the command is 4, then the snake moves north. Whenever the head of the snake moves into a new location, the tail of the snake leaves its original location. Also note that the head of the snake cannot move into any part of its body, therefore the snake can only move in its original direction, or make a left or right turn. For example, the first command of the snake should be 1, 2, or 4, otherwise the head will move into its body. Now given the initial configuration of the snake and the commands, compute the locations of all parts of the snake, starting from the head, until we run out of commands or BEFORE the head hits any part of snake body. It is guaranteed that the snake will NOT move out of the plane. Also note that it IS legal for the head of the snake to move into the OLD position of its tail. Following is an example of a case with M = 16, N = 7, x = 9, and y = 2.
Input Format
The first line contains M, N, x, and y. And the following lines each contains one integer of 1, 2, 3, or 4, which is the command mentioned above. You should read commands until reaching EOF, note that there are no more than 1000 steps.
Output Format
You should output N lines, each consists of two integers represent the grid point from head to tail.
Sample Input
4 3 2 1
2
1
4
4
3
3
3
2
2
1
4
2
1
1
4
4
Sample Output
1 1
1 2
0 2
Test Data
You can download the test data (which JudgeGirl uses) from here.
pangfengliu
commented
9 years ago
Task Description
Write a program to simulate a snake on a plane. The plane is a M by M (1 ≤ M ≤ 100) grid where (0, 0) is at the upper-left corner. Initially the snake is of length N (N ≥ 3) and facing east, and its head is locating at (x, y). That is, the snake occupied (x, y), (x - 1, y), ... (x - N + 1, y) grid points (N - 1 ≤ x < M). Now we give a sequence of commands to this snake so it moves around in this plane. If the command is 1, then the snake moves east. If the command is 2, then the snake moves south. If the command is 3, then the snake moves west. If the command is 4, then the snake moves north. Whenever the head of the snake moves into a new location, the tail of the snake leaves its original location. Also note that the head of the snake cannot move into any part of its body, therefore the snake can only move in its original direction, or make a left or right turn. For example, the first command of the snake should be 1, 2, or 4, otherwise the head will move into its body. Now given the initial configuration of the snake and the commands, compute the locations of all parts of the snake, starting from the head, until we run out of commands or BEFORE the head hits any part of snake body. It is guaranteed that the snake will NOT move out of the plane. Also note that it IS legal for the head of the snake to move into the OLD position of its tail. Following is an example of a case with M = 16, N = 7, x = 9, and y = 2.
Input Format
The first line contains M, N, x, and y. And the following lines each contains one integer of 1, 2, 3, or 4, which is the command mentioned above. You should read commands until reaching
EOF, note that there are no more than 1000 steps.Output Format
You should output N lines, each consists of two integers represent the grid point from head to tail.
Sample Input
4 3 2 1 2 1 4 4 3 3 3 2 2 1 4 2 1 1 4 4
Sample Output
1 1 1 2 0 2
Test Data
You can download the test data (which JudgeGirl uses) from here.