問題一覧 > 通常問題

No.367 The Knight's Transformation

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 152
作問者 : 🍡yurahuna / テスター : 紙ぺーぱー
お気に入りにしたユーザー ProblemId : 996 / 自分の提出
問題文最終更新日: 2026-06-25 08:39:14
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
yukicoder contest 136 (順位表) の他の問題:

Problem Statement

You are playing a game that uses a chess piece.
In this game, played on a chessboard with $H$ rows and $W$ columns, you clear the game by moving the piece from the start square to the goal square.
At the beginning of the game, the piece is placed on the start square, and at this point the piece is a knight.
You advance the game by moving this piece, but
some squares of the chessboard are red squares, and
when the piece stops on a red square, it changes from a knight into a "mini-bishop" (described later).
Similarly, when the piece stops on a red square while it is a mini-bishop, it changes into a knight.
That is, the rules regarding red squares are described as follows.
(Here, moving the piece 1 time counts as "1 move".)

  • If "the piece is a knight at the time move $k$ starts" and "the destination square of move $k$ is a red square", then
    from move $ k + 1 $ until it next stops on a red square, the piece is a mini-bishop.
  • If "the piece is a mini-bishop at the time move $k$ starts" and "the destination square of move $k$ is a red square", then
    from move $ k + 1 $ until it next stops on a red square, the piece is a knight.
The moves of the knight and the mini-bishop are as follows.
(In the description below, the square in row $i$ and column $j$ is denoted by $(i, j)$.)

  • When a knight is at position $(i, j)$, the positions it can move to next are $ (i \pm 1, j \pm 2), (i \pm 2, j \pm 1) $.
  • When a mini-bishop is at position $(i, j)$, the positions it can move to next are $ (i \pm 1, j \pm 1) $.
  • However, neither the knight nor the mini-bishop can leave the chessboard.
As diagrams, the moves of the knight (left) and the mini-bishop (right) are as follows.
N denotes the position of the knight (kNight), B denotes the position of the mini-bishop (mini-Bishop), and squares with a circle are the squares it can move to.



Now, what is the minimum number of moves in which you can clear this game?

Input

$H$ $W$
$s_1$
$s_2$
.
.
.
$s_H$

  • Line 1 contains the number of rows $H$ and the number of columns $W$ $ (1 \leq H \leq 500, 1 \leq W \leq 500) $ of the chessboard as space-separated integers.
  • Lines 2 through $ H + 1 $ give the information of each square of the chessboard. On line $i + 1$, the $j$-th character of the string $s_i$ represents the information of the square in row $i$ and column $j$.
    The meaning of each character is as follows.
    • 'S' : the start square
    • 'G' : the goal square
    • 'R' : a red square
    • '.' : any other square
    No other characters appear in $s_i (1 \leq i \leq H)$, and 'S' and 'G' each appear exactly 1 time.

Output

Print on 1 line the minimum number of moves required to move the piece from the start square to the goal square.
If the piece cannot reach the goal square, print -1.
Print a newline at the end.

Sample

Sample 1
Input
4 4
...G
.RR.
.RR.
S...
Output
3

For example, moving (4, 1) -> (2, 2) -> (3, 3) -> (1, 4) clears the game in the minimum number of moves.
In this case, the piece changes as knight -> mini-bishop -> knight.

Sample 2
Input
3 4
...G
....
S...
Output
3

In this example, the chessboard has no red squares. For example, moving (3, 1) -> (1, 2) -> (3, 3) -> (1, 4) clears the game in the minimum number of moves.

Sample 3
Input
3 3
.R.
RGR
SR.
Output
-1

In this example, the piece cannot reach the goal square.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。