No.3545 Robot on Torus (Python)
タグ : / 解いたユーザー数 15
作問者 :
Rho
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 exists 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 print $i, j$ separated by a space.
If the operations do not terminate, print loop instead.
A trailing newline or trailing spaces do not matter. You may also separate the values with a newline instead of a space.
Score
Intended solution: $137$ bytes
Score Formula
If 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 score among the source codes submitted to this problem.
Sample Program (Python)
An example solution in Python is shown below. By submitting this code, you can obtain $100$ points.
H, W = map(int, input().split())
S = [input() for _ in range(H)]
ri = -1
rj = -1
for i in range(H):
for j in range(W):
if S[i][j] == 'R':
ri = i
rj = j
break
visited = [[False] * W for _ in range(H)]
finished = False
while not visited[ri][rj]:
visited[ri][rj] = True
ri += 1
if ri == H:
ri = 0
rj += 1
if rj == W:
rj = 0
if S[ri][rj] == '#':
finished = True
break
if finished:
ri -= 1
if ri == -1:
ri = H - 1
rj -= 1
if rj == -1:
rj = W - 1
print(ri + 1, rj + 1)
else:
print("loop")
Sample
Sample 1
Input
4 4 ..R# #.#. .... ##..
Output
3 1
The robot is initially placed on $(1, 3)$. The operations then move it to $(2, 4), (3, 1)$ in order, after which no more operations can be performed because of the obstacle cell at $(4, 2)$.
Therefore, print $(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, print loop.
Sample 3
Input
15 39 ........######...#####.....####........ ........#.##.R..##...##...##..##....... ..........##....#........##............ ..........##.....#####...##............ ..........##.........##..##..###....... ..........##....##...##...##..##....... .........####....#####.....#####....... ....................................... .####.....####..##...##..#######...##.. ..##.......##...##...##...##...#..####. ..##.......##....##.##....##.#....####. ..##.......##....##.##....####.....##.. ..##...#...##.....###.....##.#.....##.. ..##..##...##.....###.....##...#....... .#######..####.....#.....#######...##..
Output
5 17
TSG LIVE! 16 Live Code Golf Day 2 will be broadcast at the May Festival on 5/17.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。