No.1572 XI

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 :

maguro / テスター :

KoD

blackyuki

PCTprobability

2 ProblemId : 6283 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-06-27 13:39:00

問題文

縦 $H$ マス、横 $W$ マスの正方形に区切られたグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表します。

$A_{i, j}$ が.のときは $(i, j)$ には何もないことを表し、#のときは $(i, j)$ に立方体のブロックが置かれていていることを表します。

今 $(s_{y}, s_{x})$ に、サイコロが $1$ の目を上にして置かれています。サイコロは上下左右 $4$ 方向に転がすことが可能ですが、ブロックが置かれているマスやグリッドの外には転がせません。

このとき、 $(g_{y}, g_{x})$ に $1$ の目が上になっている状態にサイコロを転がすことは可能でしょうか？可能ならば転がす最小回数を求めてください。

入力

 $H W$ 
 $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}$ 
 $⋮$ 
 $A_{H, 1} A_{H, 2} \dots A_{H, W}$

$2 \leq H, W \leq 1000$
$1 \leq s_{y}, g_{y} \leq H$
$1 \leq s_{x}, g_{x} \leq W$
$(s_{y}, s_{x}) \neq (g_{y}, g_{x})$
$A_{i, j}$ は.か#のいずれか
$A_{s_{y}, s_{x}}, A_{g_{y}, g_{x}}$ は.

出力

$(g_{y}, g_{x})$ に $1$ の目が上になっている状態にサイコロを転がすことが不可能な場合、-1を出力してください。

可能な場合、 $(g_{y}, g_{x})$ に $1$ の目が上になっている状態にサイコロを転がす最小回数を出力してください。

最後に改行してください。

サンプル

サンプル1

入力

4 4
1 1
4 4
....
..##
#...
#...

出力

$(1, 1), (2, 1), (2, 2), (3, 2), (3, 3), (4, 3), (4, 4)$ の順に転がすのが最適です。

サンプル2

入力

3 2
1 1
3 2
..
..
..

出力

$(1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (2, 1), (2, 2), (3, 2)$ の順に転がすのが最適です。

サンプル3

入力

4 4
1 1
4 4
....
.#..
...#
.#..

出力

-1

どのように転がしても $(g_{y}, g_{x})$ に $1$ の目が上になるようにサイコロを転がすことが出来ません。

サンプル4

入力

4 4
1 1
4 4
....
.#..
..##
.#..

出力

-1

そもそも $(g_{y}, g_{x})$ にサイコロを転がすことが出来ません。

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