問題一覧 > 通常問題

No.2646 Cycle Maze

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : matcharate12matcharate12 / テスター : shinnshinnshinnshinn
0 ProblemId : 10585 / 自分の提出
問題文最終更新日: 2024-02-26 14:52:21

訂正について

  • 2/25 19:33 時点: 問題文のご指摘をいただきましたので、一部訂正しました。
  • 2/26 14:52 時点: ご指摘から、紛らわしい部分がありましたので問題文を一部訂正しました。

    • 時間制限について

    実行が遅い言語でもACできるように、今回は緩めに時間制限を設けています。

    問題文

    縦 $H$ 、横 $W$ の $0,1,...,9$ までの数字からなる盤面 $A$ があります。
    盤面において、上から $i\ (1\le i\le H)$ 行目左から $j\ (1\le j\le W)$ 列目の座標を $(i,j)$ と表すことにし、$(i,j)$ のマスに書かれた数字を $A_{i,j}$ と表すことにします。

    matcharate君は、最初盤面上の $(S_Y,S_X)$ に位置しており、$(G_Y,G_X)$ にたどり着きたいと思っています。またこのときターン $0$ とします。
    今から各ターン $k=1,2,\dots$ において、次のようなフェーズを介して移動を行います。ただしここではターン $k$ での盤面 $A$ の状態を $B$ と表すことにします。特にターン $0$ のとき $B_{i,j}=A_{i,j}$ です。

    • [数字変更フェーズ]: 最初に $1\le i\le H,1\le j\le W$ の整数組 $(i,j)$ に対し、$B_{i,j}$ を $(B_{i,j}-1)\ \text{mod}\ (A_{i,j}+1)$ に変更する。
      • すなわち $B$ のすべてのマスの数字を $1$ ずつ減らし、$0$ であるマスではターン $0$ の時の盤面の状態のマスの数字 $A_{i,j}$ に再び戻す。
    • [移動フェーズ]: 次に、今いる座標 $(y,x)$ として、次のいずれかのマスに移動する。このとき次に移動先のマス(または今いるマス)に書かれた数字が $1$ 以上でなければならない。
      • $(y+1,x)$
      • $(y-1,x)$
      • $(y,x+1)$
      • $(y,x-1)$
      • $(y,x)$ (そのマスから動かない)
    $1$ 回の[移動フェーズ]を終えたと同時に、ターンは $1$ ずつ増加していきます。また、ここでゲームオーバーになる条件は次のようになります。

  • [移動フェーズ]において、まだ目標を達成していない(すなわち $(G_Y,G_X)$ に到達していない)時、移動先のマス(動かないときは今いるマス)に書かれた数字がすべて $0$ であり、どのマスにも移動できないとき
  • 現在のターン数が $T$ 以上となったとき

    • ゲームオーバーとならずに適切に行動を行うことによって、matcharate君の目標を達成させるような移動方法は存在しますか？
    ただし、各マスには何回でも移動できるものとします。

    また[数字変更フェーズ]において今いるマスの数字が $0$ となることがありますが、移動する前の数字の意味は考えないものとすることに注意してください(すなわちゲームオーバーの対象になりません)。

    $A\ \text{mod}\ B$ とは 整数 $A,B$ において $A\ \text{mod}\ B$ とは、「$A$ を $B$ で割ったあまり」を表します。
    一般に $\lfloor\frac{A}{B}\rfloor=q,\ A\ \text{mod}\ B=r$ ( $r$ は非負整数) として、$A=Bq+r$ と表せることが知られており、これを満たす $r$ は $0\le r\lt B$ の範囲で一意に定まります。
    この $r$ は定義に従い、「$A$ を $B$ で割ったあまり」となります。すなわち余りは非負整数となることに注意してください。

    入力

    $H$ $W$ $T$
$S_Y$ $S_X$
$G_Y$ $G_X$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\dots$ $A_{H,W}$

    • $1\le H,W\le 200$
    • $H\times W\gt 1$
    • $1\le T\le 600$
    • $1\le S_Y,G_Y\le H$
    • $1\le S_X,G_X\le W$
    • $(S_Y,S_X)\ne (G_Y,G_X)$
    • $0\le A_{i,j}\le 9$
    • $A_{S_Y,S_X}\ne 0$

    出力

    目標を達成できる移動方法が存在するなら Yes 、存在しないなら No を出力してください。

    サンプル

    サンプル1
    入力
    3 3 7
1 1
3 3
103
210
232
    出力
    Yes

    例えば次のように移動すると良いです。

    ・ターン $0$ の移動: $(1,1)$ から $(2,1)$ へ移動する。移動した時点(ターン $1$ )で各マスは次のようになる。 

    002
100
121
    ・ターン $1$ の移動: $(2,1)$ から $(2,2)$ に移動する。移動した時点(ターン $2$ )で各マスは次のようになる。 
    101
010
010
    ・ターン $2$ の移動: $(2,2)$ から $(2,1)$ へ移動する。ターン $2$ が終わり、ターン $3$ では各マスは次のようになる。 
    000
200
202
    ・ターン $3$ の移動: $(2,1)$ から $(3,1)$ へ移動する。ターン $3$ が終わり、ターン $4$ では各マスは次のようになる。 
    103
110
131
    ・ターン $4$ の移動: $(3,1)$ から $(3,2)$ へ移動する。ターン $4$ が終わり、ターン $5$ では各マスは次のようになる。 
    002
000
020
    ・ターン $5$ の移動: $(3,2)$ から $(3,3)$ へ移動する。ターン $5$ が終わり、ターン $6$ では各マスは次のようになる。 
    101
210
212
    ターン $6$ において、$(3,3)$ に移動した時点でマスの数字は $0$ でありません。またターン $7$ に達していません。よって目標を達成することができます。

    サンプル2
    入力
    2 2 2
1 1
2 2
12
22
    出力
    No

    どう移動しようと $(2,2)$ に移動した時点でマスの数字は $0$ となってしまい、ゲームオーバーとなります。よって目標を達成できません。

    サンプル3
    入力
    5 5 9
1 1
5 5
99999
99999
99999
99999
99999
    出力
    Yes

    最短経路を達成するような移動を行うことで目標を達成することができます。このときゴールのマス $(5,5)$ の数字は $1$ です。

    サンプル4
    入力
    2 2 600
2 1
2 2
99
90
    出力
    No

    ゴールのマスが最初から $0$ となることもあります。

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