로봇 (robot)

로봇 하나가 $n \times m$ 격자로 모델링된 필드 위에 놓여 있다. 이 격자의 일부 칸은 벽이다.

로봇은 $4$가지 종류의 명령을 받는다: up, down, left, right.

로봇이 현재 좌표 $(x,y)$에 있다고 하자. 각 명령을 실행했을 때의 효과는 다음과 같다.

• up: $x=0$이거나 $(x-1,y)$가 벽이면 로봇은 움직이지 않는다. 그렇지 않으면 로봇은 $(x-1,y)$로 이동한다.
• down: $x=n-1$이거나 $(x+1,y)$가 벽이면 로봇은 움직이지 않는다. 그렇지 않으면 로봇은 $(x+1,y)$로 이동한다.
• left: $y=0$이거나 $(x,y-1)$이 벽이면 로봇은 움직이지 않는다. 그렇지 않으면 로봇은 $(x,y-1)$로 이동한다.
• right: $y=m-1$이거나 $(x,y+1)$이 벽이면 로봇은 움직이지 않는다. 그렇지 않으면 로봇은 $(x,y+1)$로 이동한다.

로봇의 시작 위치는 $(a,b)$ 또는 $(c,d)$ 중 하나라는 것을 알고 있다. 로봇이 $(a,b)$와 $(c,d)$ 중 어느 곳에서 시작하더라도 항상 $(0,0)$에서 끝나게 하는, 최대 $q$개의 명령으로 이루어진 순서를 찾아라. 문제의 제약 조건을 만족하는 모든 입력에 대해 해가 존재함을 증명할 수 있다.

구현 세부사항

다음 프로시저를 구현해야 한다.

void construct_instructions(bool[][] g, int q, int a, int b, int c, int d)

• $g$: 크기가 $n \times m$인 2차원 배열이다. 각 $i,j$ ($0 \le i \le n-1$, $0 \le j \le m-1$)에 대해, 칸 $(i,j)$가 벽이면 $g[i][j]=1$이고, 그렇지 않으면 $g[i][j]=0$이다.
• $q$: 사용할 수 있는 명령의 최대 개수이다.
• $a,b,c,d$: 로봇의 가능한 시작 위치는 $(a,b)$ 또는 $(c,d)$이다.

이 프로시저는 명령 순서를 구성하기 위해 다음 프로시저 중 하나 이상을 호출해야 한다.

void up()
void down()
void left()
void right()

마지막 명령을 추가한 뒤 construct_instructions는 반환해야 한다.

예제

다음 호출을 생각해 보자.

construct_instructions([[0,0],[0,1]], 700, 1, 0, 0, 1)

격자에는 $(1,1)$에 벽이 하나 있다.

로봇이 $(1,0)$에서 시작한다면, up()을 실행한 다음 left()를 실행했을 때 다음과 같은 일이 일어난다.

마찬가지로 로봇이 $(0,1)$에서 시작한다면, up()을 실행한 뒤에도 $(0,1)$에 머물고 left()를 실행한 뒤 $(0,0)$으로 이동한다.

이 구성을 출력하려면 프로그램은 반환하기 전에 up()을 호출한 다음 left()를 호출해야 한다.

제약 조건

• $1 \le n \le 10$
• $1 \le m \le 10$
• $0 \le a \le n-1$
• $0 \le b \le m-1$
• $0 \le c \le n-1$
• $0 \le d \le m-1$
• $g[0][0]=g[a][b]=g[c][d]=0$
• 로봇을 $(a,b)$에서 $(0,0)$으로 이동시키는 유한한 명령 순서가 존재한다.
• 로봇을 $(c,d)$에서 $(0,0)$으로 이동시키는 유한한 명령 순서가 존재한다.
• $q=700$

서브태스크

1. (20점) $n \le 2$
2. (20점) $g[i][j]=0$ (모든 $0 \le i \le n-1$, $0 \le j \le m-1$에 대해)
3. (20점) $a=c$, $b=d$
4. (40점) 추가 제약 조건 없음

샘플 그레이더는 다음 형식으로 입력을 읽는다.

• 1번째 줄: $n\ m\ q\ a\ b\ c\ d$
• $2+i$번째 줄 ($0 \le i \le n-1$): $g[i][0]\ g[i][1]\ \ldots\ g[i][m-1]$

샘플 그레이더는 다음 형식으로 출력을 인쇄한다.

• 1번째 줄: 사용한 명령의 개수
• 2번째 줄: 사용한 모든 명령을 포함하는 문자열. up(), down(), left(), right()를 호출할 때마다 그레이더는 각각 단일 문자 U, D, L, R을 인쇄한다.