No.340 雪の足跡
Note
この問題は制約の都合上 C++/Java/C# などの速い言語を使わないと全てのテストケースを通すことが出来ないのでご注意ください。
00,01,02 のテストケースはLLでも通すことが可能です。
[参考]
writerが想定解法で解いたときのおおよその実行時間は以下のようになっています。
- C++: 0.45 sec
- Python2: 6 sec(TLE)
- PyPy2: 1.5 sec(TLE)
入出力のせいなのかC#も相当しんどいみたいです。今のところお一人のみC#でAC(758 ms)しています.
問題文
Manaさんが朝目を覚ますと、街中に身長よりも高い雪が積もっていました。
今日はMitsuruさんの家に遊びに行こうと思っていたのに、このままでは遊びに行くどころか外にも出られません。
そこでManaさんは、雪を掘り進んで出かけていった大人達の通った跡を辿って出かけることを思いつきました。
ただManaさんは身体が弱く、長時間外に居るとすぐ風邪を引いてしまうためあまり長距離を歩かせられません。
心配した父親は、Mitsuruさんの家に行くのにどれだけ歩かないといけないか調べてあげることにしました。
Manaさんの住んでいる街は横幅 $W$、縦幅 $H$ の長方形の街で、$W \times H$個の正方形の区画から構成されます。
各区画は一番南西の区画を $0$ 番として番号付けされており、$0$ 番の区画から東に $w$、北に $h$ 進んだ所にある区画の番号は$w + h \times W$ $(0 \le w \lt W,\ 0 \le h \lt H)$ です。
ある区画から移動できる方向は東西南北の4方向であり、隣接した区画間の距離は全て1です。
Manaさんの家は区画 $0$ 、Mitsuruさんの家は区画 $ W\times H-1$ にあるものとします。
大人達のお出かけは各々の家のある区画から始まり、今居る区画から直進して別の区画で立ち止まる、という行動の繰り返しによってなされます。
この直進の際に、隣接する二つの区画 $B_1$, $B_2$ の間を通過した大人が存在すると、Manaさんも $B_1$ と $B_2$ の間を行き来することが出来ます。
例えば以下の図で大人達が通った経路が黒の矢印だったとき、ManaさんがMitsuruさんのところにたどり着ける経路は赤と青の矢印になります。
Manaさんが大人達の進んだ方向とは逆方向に進めることに注意して下さい。
大人達の移動経路が与えられるので、Manaさんの家のある区画からMitsuruさんの家のある区画にたどり着く最短距離を求めてください。
入力
$W \ H \ N \\ M_1 \\ B_{1 \ 0} \ B_{1 \ 1} \ ... \ B_{1 \ M_1} \\ . \\ . \\ M_N \\ B_{N \ 0} \ B_{N \ 1} \ ... \ B_{N \ M_N} $
各行の要素は空白で区切られています。
$1$行目には街の横幅 $W$, 縦幅 $H$, 出かけた大人の数 $N$ が与えられます。
$2$行目以降には大人達のお出かけの経路の情報が与えられます。
$M_i$は大人 $i$ がお出かけの際に立ち止まった回数、$B_{i \ 0}$ は大人 $i$ の家のある区画、$B_{i \ j}$ $(j = 1,..,M_i)$ は大人 $i$ が $j$ 番目に立ち止まった区画の番号を示します。
$B_{i \ j}$ から $B_{i \ j+1}$ への移動は東西南北いずれかの方向への直進で行われ、立ち止まるごとに直進の方向が変わるものとします。
入力は全て整数であり、以下の制約を満たします。
$ 1 \le W,H \le 10^3 $
$ 0 \le N \le 10^3 $
$1 \le M_i \le 10^3 $
$0 \le B_{i \ j} \lt W \times H $
$j = 0,1,..,M_i-1$ について、
$B_{i \ j} \neq B_{i \ j+1} \land (\ B_{i \ j} \equiv B_{i \ j+1} \pmod W \lor \lfloor B_{i \ j} \div W \rfloor = \lfloor B_{i \ j+1} \div W \rfloor \ )$
が成り立つことが保証されます。※ $\lfloor x \rfloor$ は床関数です。
<追加制約>
00,01,02 のテストケースは
$ W,H,N,M_i \le 3.0 \times 10^2 $
を満たします。
出力
Manaさんが大人達の通った跡を通ってMitsuruさんの家のある区画にたどり着く最短距離を出力して下さい。たどり着けない場合は"Odekakedekinai.."を出力して下さい。
最後に改行してください。
サンプル
サンプル1
入力
3 3 2 2 0 1 4 2 4 7 8
出力
4
$0→1→4→7→8$
の経路でたどり着くことが出来ます。
サンプル2
入力
4 4 3 3 6 2 0 12 3 3 11 8 4 3 15 13 5 6
出力
6
問題文で例に挙げたケースです。
サンプル3
入力
5 3 0
出力
Odekakedekinai..
出かけた大人が一人も居なかったようです。
サンプル4
入力
3 3 1 5 8 6 3 5 2 0
出力
8
隣接した二つの区画それぞれを大人が通過していても、その二区画間で通過が起こっていないとManaさんが通れないことに注意して下さい。
例えば$1$と$4$は大人が通過していますが、この二区画間で通過が起こっていないので$1→4$と通ることはできません。
サンプル5
入力
3 3 1 9 1 2 5 3 6 7 1 2 8 7
出力
Odekakedekinai..
Manaさんの住む区画だけが孤立していてお出かけが出来ません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。