問題一覧 > 通常問題

No.124 門松列(3)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 122
作問者 : yuki2006yuki2006
3 ProblemId : 222 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-05-24 14:35:05

問題文

前回の門松列の傾向と対策問題で、出そうと思っていた門松列問題を当てられたので万事休すかとおもいきや、1次元列を離れ2次元グリッドに飛び出す事になりました。

ここ最近何度も出てますが「門松列」とは、「3つの竹の長さの降順で2番目が、左または右側になっているもの」、「3つの長さはすべて異なる」という条件を満たすものである。

ここで、$W\times H$の平面グリッドで各マスは$1$から$9$の数値が書かれたマスが与えられます。
それらのマスを現在地から1ステップごとに上下左右1マス(マンハッタン距離1)だけ進むことができます。
ただし、直近2回のいた場所と新しいマスの数値の順番が、門松列をなしてなければなりません。

つまり、 $A$を到達したマスの数値の履歴として$A_i$を$i$番目に通ったマスの数値とし、
$isKadomatsuSequence$を門松列かどうか判定する関数だとすると。

$isKadomatsuSequence(A_{i−2},A_{i-1},A_{i})$
が、$i\ge 3$ですべてtrueになる経路にならなくてはならない。
(最初の2ステップまでは、値が3つないので門松列が成り立ってなくても良い)

左上$(1,1)$がスタート地点とし、右下$(W,H)$がゴール地点であるときに、
ゴール地点にたどり着くまでの最短ステップ数を出力してください。
この条件でゴールできなければ -1を出力してください。

入力

$W$ $H$
$M_{1,1}\ M_{2,1} \dots M_{W,1}$
$M_{1,2}\ M_{2,2} \dots M_{W,2}$
$\dots\dots\dots\dots\dots\dots$
$M_{1,H}\ M_{2,H} \dots M_{W,H}$

入力は全て整数で与えられる。
$2\le W \le 100=10^2$
$2\le H \le 100=10^2$
$1\le M_{i,j}\le 9$
$1\le i \le W,1\le j \le H$

出力

スタート地点からゴール地点にたどり着くまでの最短ステップ数を求めてください。
この条件でゴールできなければ -1を出力してください。
最後に改行をしてください。

サンプル

サンプル1
入力
3 3
1 2 3
3 2 1
1 4 1
出力
4

$[1,3,2,4,1]$と進むことにより、
$[1,3,2]$,$[3,2,4]$,$[2,4,1]$ のようにそれぞれ門松列になっている。答えは門松列数+1ということもできます。

サンプル2
入力
2 2
1 3
2 2
出力
2

門松列1つだけでゴールです。

サンプル3
入力
4 4
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
出力
-1

この場合、ゴールすることはできません。

サンプル4
入力
3 3
5 4 1
6 6 9
2 8 8
出力
6

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