問題一覧 > ショートコード

No.3544 Robot on Torus (C++)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 19
作問者 : alcea / テスター : tRue naka9 Rho
お気に入りにしたユーザー ProblemId : 13280 / 自分の提出
問題文最終更新日: 2026-05-16 12:27:38
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
TSG LIVE! 16 コードゴルフコンテスト (順位表) の他の問題:

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.
Determine whether the operations terminate, and if they do, find the cell where the robot is finally placed.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。