Roboti
레이팅 미적용의견: 0
Kile, a board games enthusiast, recently discovered the game Robots. The game
consists of a board with \(n\) rows and \(m\) columns and one robot. The field (1, 1) is
the t\(op-le\)ft field of the board, while the field (n, m) is the bott\(om-ri\)ght.
At the beginning, the robot is positioned on some field (x, y) (\(x-th\) row, \(y-th\)
column), and the player can direct it in one of the four directions: up, down, left,
or right. Depending on the chosen direction, it will move in that direction until it
encounters its goal or a special field on the board. If at any point it wants to exit
the board, it wraps around to the other side. For example, if it is located at the field (n, 3) and wants to
move down, it will arrive at the field (1, 3).
The board has three types of fields:
• Empty fie\(ld - th\)e robot continues moving in the same direction
• Left turn fie\(ld - wh\)en the robot steps on this field, it will turn left by 90° and continue moving
• Right turn fie\(ld - wh\)en the robot steps on this field, it will turn right by 90° and continue moving
Most fields on the board are empty, only \(k\) of them are left or right turn fields.
The game consists of \(q\) rounds. In the \(i-th\) round of the game, the robot will be placed on the field
(\(a@@RISE_MATH_BLOCK_0@@i\), d\(i\)) using the minimum number of turns, or determine that it is
impossible.
After playing this game several times, Kile realized that it is more challenging than it initially seemed.
That is why he needs your help now. Help him determine the minimum number of turns required for each
Note: If the robot starts or finishes its path on a left or right turn field, that turn is not counted.
Subtask 1 (10 points): \(k = 0\)
Subtask 2 (13 points): n, \(m \le 300\), \(q \le 10\)
Subtask 3 (49 points): n, \(m \le 300\)
Subtask 4 (38 points): No additional constraints.
The first line contains integers \(n\), \(m\) and \(k\) (\(1 \le n\), \(m \le 10^{6}\), \(0 \le k \le 10^{5}\)), the number of rows, columns
and n\(on-em\)pty fields on the board.
The \(i-th\) of the following \(n\) lines contains integers \(x@@RISE_MATH_BLOCK_0@@i\) (\(1 \le x@@RISE_MATH_BLOCK_1@@i \le m\), s\(i\) =
‘L’ors\(i\) = ‘R’), the row and column of \(i-th\) turn field and the type of turn. If \(s@@RISE_MATH_BLOCK_2@@i\) = ‘R’ then it is a right turn field.
The next line contains integer \(q\) (\(1 \le q \le 3 \cdot 10^{5}\)), the number of rounds.
The \(i-th\) of the following \(q\) lines contains integers \(a@@RISE_MATH_BLOCK_3@@i\), c\(i \le n\), \(1 \le b\)\(i\), d\(i \le m\)), the starting
position and the goal.
In the \(i-th\) of the following \(q\) lines output the minimal number of turns for the \(i-th\) round of the game or
’-1’ if it is impossible to reach the goal.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(k = 0\) |
2 | 13점 | n, \(m \le 300\), \(q \le 10\) |
3 | 49점 | n, \(m \le 300\) |
4 | 38점 | No additional constraints. |
2 2 2
1 1 L
2 2 R
5
1 1 2 2
2 1 1 2
1 1 1 2
2 1 1 1
2 2 2 1-1
1
0
0
03 3 4
1 1 L
1 3 L
2 1 L
3 3 L
7
1 1 3 3
3 3 2 1
3 1 2 2
2 3 1 2
2 3 3 1
1 2 3 2
3 3 2 21
2
1
1
1
0
34 4 8
1 1 R
1 3 L
2 2 R
2 4 L
3 1 L
3 3 L
4 2 L
4 4 L
7
1 2 1 4
2 2 3 4
4 4 3 2
4 1 4 4
4 2 3 1
1 2 2 3
2 4 2 32
1
1
0
-1
5
0Clarification of the second example:
First round: We start at (1, 1). If we direct the robot to the left, it will arrive at (1, 3) in the next step
because it wanted to exit the board, so it wraps around to the other side. Field (1, 3) is a left turn field,
so the robot is now directed downwards. After two more steps, it will be at the desired goal (3, 3).
Second round: We start at (3, 3). If we direct the robot upwards, it will arrive at (1, 3) in two steps,
where it will be directed to the left due to the left turn field. After two steps, it will be at the field (1, 1),
which is also a left turn field, so it will be directed downwards. In the next step, it will be at the desired
goal (2, 1).
평가 및 의견
Roboti
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Roboti