루미 알고리즘

#1389플래티넘Vvvvvv

PO 2016 결선코딩출제 Pär Söderhjelm영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

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.

Input

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 ≤ x_1, x_2 ≤ W and 0 ≤ y_1, y_2 ≤ 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.

Output

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).

Scoring

Your solution will be tested on a set of test case groups. In order to receive points for a group, you need to solve all test cases in the group.

GroupPointsLimitsConstraints
120W,H ≤ 10, N ≤ 25, there is a solution with at most 10 movesthe sequence does not need to be as short as possible.
215W,H ≤ 20, N ≤ 200, there is a solution where you do not need to use Vthe sequence does not need to be as short as possible.
315W,H ≤ 50, N ≤ 2000the sequence does not need to be as short as possible.
420W,H ≤ 10, N ≤ 50the sequence needs to be as short as possible.
530W,H ≤ 100, N ≤ 5000the 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
출력
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
출력
HGVHHHHGHHVVHHHGHVHH

예제 3

입력
2 1 2
0 0 1 0
1 1 2 1
출력
Inte

출처 표기

출처: Programmeringsolympiaden 2016년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.