No.3544 Robot on Torus (C++)
Problem Statement
There is an $H \times W$ grid. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i, j)$. The state of each cell is represented by a character $S_{i, j}$: . means an empty cell, # means an obstacle cell, and R means the robot cell.
This grid is also toroidal. That is, the cell to the right of cell $(i, W)$ is $(i, 1)$, and the cell below cell $(H, j)$ is $(1, j)$.
There is exactly one robot cell in the grid, and initially one robot is placed on the robot cell. TSG-kun repeats the following operation until it can no longer be performed.
- If the cell to the lower right of the cell where the robot is placed is not an obstacle cell, move the robot to the lower-right cell.
Input
$H\ W$
$S_{1, 1} S_{1, 2}, \ldots, S_{1, W}$
$S_{2, 1} S_{2, 2}, \ldots, S_{2, W}$
$\vdots$
$S_{H, 1} S_{H, 2}, \ldots, S_{H, W}$
- $1 \leq H, W \leq 1000$
- $H, W$ are integers
- $S_{i, j}$ is one of
.#R - There is exactly one $(i, j)$ such that $S_{i, j} =$
R
Output
If the operations terminate, let $(i, j)$ be the cell where the robot is finally placed, and output $i, j$ separated by a space.
If the operations do not terminate, output loop instead.
A trailing newline or trailing spaces may or may not be present. You may also separate the values with a newline instead of a space.
Score
Intended solution: $157$ bytes
Score formula
When the code length of a submitted source code is $x$ and the code length of the intended solution of this problem is $y$, the score of that source code is $\max(500 - x + y, 100)$ points.The score for this problem is the maximum of the scores of the source codes submitted to this problem.
Sample Program (C++)
An example solution in C++ is shown below. Submitting this code earns you $100$ points.
#include <bits/stdc++.h>
using namespace std;
int main() {
int H, W;
cin >> H >> W;
vector<string> S(H);
for(int i = 0; i < H; i++) {
cin >> S[i];
}
int ri = -1, rj = -1;
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
if(S[i][j] == 'R') {
ri = i;
rj = j;
break;
}
}
}
vector<vector<bool>> visited(H, vector<bool>(W, false));
bool finished = false;
while(!visited[ri][rj]) {
visited[ri][rj] = true;
ri++;
if(ri == H) {
ri = 0;
}
rj++;
if(rj == W) {
rj = 0;
}
if(S[ri][rj] == '#') {
finished = true;
break;
}
}
if(finished) {
ri--;
if(ri == -1) {
ri = H - 1;
}
rj--;
if(rj == -1) {
rj = W - 1;
}
cout << ri + 1 << " " << rj + 1 << endl;
}
else {
cout << "loop" << endl;
}
}
Sample
Sample 1
Input
4 4 ..R# #.#. .... ##..
Output
3 1
The robot is initially placed at $(1, 3)$. The operations then move it to $(2, 4), (3, 1)$, after which the operation can no longer be performed because of the obstacle cell at $(4, 2)$.
Therefore, output $(3, 1)$, the cell where the robot is finally placed, separated by a space.
Sample 2
Input
3 3 ... .R. ...
Output
loop
The robot moves as $(2, 2), (3, 3), (1, 1), (2, 2), (3, 3), \ldots$, and the operations never terminate.
Therefore, output loop.
Sample 3
Input
15 39 ........######...#####.....####........ ........#.##.R..##...##...##..##....... ..........##....#........##............ ..........##.....#####...##............ ..........##.........##..##..###....... ..........##....##...##...##..##....... .........####....#####.....#####....... ....................................... .####.....####..##...##..#######...##.. ..##.......##...##...##...##...#..####. ..##.......##....##.##....##.#....####. ..##.......##....##.##....####.....##.. ..##...#...##.....###.....##.#.....##.. ..##..##...##.....###.....##...#....... .#######..####.....#.....#######...##..
Output
5 17
TSG LIVE! 16 Live Code Golf Day 2 will be broadcast on 5/17 at the May Festival.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Rho