시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 0 0 0 0.000%

문제

Platform games is an old video game genre, where you move across platforms hanging in the air. Vvvvvv is a platform game where you cannot jump, but instead are able to switch between regular gravity, which causes you to fall downwards, and anti-gravity, which causes you to fall upwards. There are only three buttons in the game: the gravitational switch (G), the go-left-button (V) and the go-right-button (H).

Your task is to find a sequence of button presses which takes you through a maze-like level with platforms and walls, from a given start position to a given final position. In order to receive full points, the sequence needs to be as short as possible.

Figure 1: The path given by the button presses given in the second sample.

입력

The first line of the input consists of three integers $W$, $H$, and $N$: the width of the level, the height of the level, and the number of line segments. Thereafter follows $N$ lines, each with four integers $x_1$, $y_1$, $x_2$, $y_2$, where $0 \le x_1, x_2 \le W$ and $0 \le y_1, y_2 \le H$. Each of these lines describe a line segments with end points $(x_1, y_1)$ and $(x_2, y_2)$. Every line segment is either horizontal or vertical, i.e. either $y_1=y_2$ or $x_1=x_2$ holds. The integer coordinate system can be said to divide the rectangular level into a grid, where the button V takes you one square to the left and H takes you one square to the right. If you are not standing on a platform after the movement you will fall (upwards or downwards) until you reach another platform. It is not possible to move to the left or right while falling. If you fall or walk out of the level, you lose the game. This also happens if you try to walk through a wall.

The start position is the lower left square, closest to the point (0, 0), with downwards gravity. The final position is the square in the upper right corner, closest to the point (W, H). There will always be a line segment under the start position and above the final position.

출력

If there is a solution, the program should print a string containing a letter for each button press (chosen from G, V and H). The sequence should take you from the start position to the final position, and has to be shorter than $10000$ characters. You can arrive to the ending position with gravity in either direction, but you need to have stopped falling (see the third example below).

If there is no solution, the program should print the string "Inte" (without the quotation marks).

제한

  • $W,H \le 100$
  • $N \le 5000$
  • The sequence needs to be as short as possible.

예제 입력 1

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

예제 출력 1

HGHHVH

예제 입력 2

10 9 22
0 0 2 0
2 0 2 2
1 1 1 4
0 3 1 3
1 5 4 5
3 2 3 3
3 4 3 5
4 5 4 6
4 4 4 3
4 3 6 3
6 1 8 1
5 4 7 4
7 4 7 3
7 3 8 3
8 3 8 5
8 5 7 5
6 5 6 7
6 7 4 7
0 8 5 8
8 8 8 6
8 6 10 6
7 9 10 9

예제 출력 2

HGVHHHHGHHVVHHHGHVHH

예제 입력 3

2 1 2
0 0 1 0
1 1 2 1

예제 출력 3

Inte

출처

Olympiad > Swedish Olympiad in Informatics > 2016 > Final E번

  • 문제를 만든 사람: Pär Söderhjelm