Robot (robot)

There is a robot which is placed on a field modeled as a n × 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.

Implementation details

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 × m. For each i, j(0 ≤ i ≤ n − 1, 0 ≤ j ≤ 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.

Example

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.

Constraints

• $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$

Sample grader

The sample grader reads the input in the following format:

• line 1: n m q a b c d
• line 2 + i (0 ≤ i ≤ n − 1): g[i][0] g[i][1]… 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.

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (Robot)

(robot)

There is a robot which is placed on a field modeled as a n × 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.

Implementation details

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 × m. For each i, j(0 ≤ i ≤ n − 1, 0 ≤ j ≤ 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.

Example

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.

Constraints

• $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$

Sample grader

The sample grader reads the input in the following format:

• line 1: n m q a b c d
• line 2 + i (0 ≤ i ≤ n − 1): g[i][0] g[i][1]… 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.

Execution limits

Your solution will have 1.0 second(s) execution time and 1024 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "robot.h"

void construct_instructions(std::vector<std::vector<bool>> g, int q, int a, int b, int c, int d) {
    up();
    left();
}

参考函数签名

#include "robot.h"

void construct_instructions(std::vector<std::vector<bool>> g, int q, int a, int b, int c, int d) {
    up();
    left();
}

请在 submission.cpp 中实现该函数（可 #include "problem.h" 获取题目提供的声明）。判题时你的代码会与题目提供的 grader 一起编译链接。

本题是函数题，由 grader 调用你实现的函数。

由 grader 打印判定结果，无需自行读写 stdin/stdout。

include "robot.h"

void construct_instructions(std::vector<std::vector\<bool>> g, int q, int a, int b, int c, int d) {
up();
left();
}