22022번 - Robot 서브태스크다국어언어 제한함수 구현

There is a robot which is placed on a field modeled as a $n \times m$ grid. Some of these grid cells are walls.

The robot accepts 4 types of instructions: up, down, left, right.

Suppose the robot is currently at the coordinate $(x, y)$. Then the effect of executing the instructions will be as follows:

• up : If $x = 0$ or $(x - 1, y)$ is a wall, the robot does not move. Else, the robot moves to $(x - 1, y)$
• down : If $x = n - 1$ or $(x + 1, y)$ is a wall, the robot does not move. Else, the robot moves to $(x + 1, y)$
• left : If $y = 0$ or $(x, y - 1)$ is a wall, the robot does not move. Else the robot moves to $(x, y - 1)$
• right: If $y = m - 1$ or $(x, y + 1)$ is a wall, the robot does not move. Else the robot moves to $(x, y + 1)$.

You know that the starting position of the robot is either $(a, b)$ or $(c, d)$. Find a sequence of at most q instructions such that the robot always ends up at $(0, 0)$ when the robot starts from either $(a, b)$ or $(c, d)$. It can be proven that there exists a solution for all inputs satisfying the problem constraint.

You should implement the following procedure:

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

• $g$: a 2-dimensional array of size $n \times m$. For each $i$, $j$ ($0 \le i \le n - 1$, $0 \le j \le m - 1$), $g[i][j] = 1$ if cell $(i, j)$ is a wall, and $g[i][j] = 0$ otherwise.
• $q$: the maximum number of instructions that you are allowed to use.
• $a$, $b$, $c$, $d$: the possible starting location of the robot is either $(a, b)$ or $(c, d)$

This procedure should call one or more of the following procedures to construct the sequence of instructions:

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

After appending the last instruction, construct_instructions should return.

Consider the following call:

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

The grid has a single wall at $(1, 1)$.

If the robot begins at $(1, 0)$, the following happens when up() followed by left() is executed:

Similarly, if the robot begins at $(0, 1)$, it remains at $(0, 1)$ after up() and moves to $(0, 0)$ after left().

The program should call up() followed by left() before returning to output this construction.

• $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$
• There exists a finite sequence of instructions to move the robot from $(a, b)$ to $(0, 0)$
• There exists a finite sequence of instructions to move the robot from $(c, d)$ to $(0, 0)$
• $q = 700$

The sample grader reads the input in the following format:

• line 1 : $n$ $m$ $q$ $a$ $b$ $c$ $d$
• line $2 + i$ ($0 \le i \le n - 1$): $g[i][0]$ $g[i][1]$ $\cdots$ $g[i][m - 1]$

The sample grader prints the output in the following format:

• line 1: the number of instructions used
• line 2: a string containing all the instructions used. For every call to up(), down(), left(), right(), the grader will print a single character, U, D, L or R respectively.

• robot.zip