No.971 いたずらっ子

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 126
作問者 : 沙耶花沙耶花 / テスター : shibh308shibh308
10 ProblemId : 3634 / 出題時の順位表
問題文最終更新日: 2020-01-18 00:07:30

問題文

あなたは今,競プロ公園という公園にいます.
この公園の敷地は長方形の形をしていて,南北方向に$H$マス,東西方向に$W$マスのマス目状に,$H\times W$個の区画に分かれています.
以降,北から$r$番目で西から$c$番目の区画を区画$(r,c)$と呼ぶこととします.

あなたは区画$(1,1)$から南または東に区画を1つ分移動することを繰り返し,公園の出口に隣接する区画$(H,W)$を目指します.
ここで,あなたは(方角によらず)区画を1つ分移動するのに1分かかります.

ときに,いたずらっ子があなたを妨害することがあります.
もしあなたがいたずらっ子が待ち構えている区画に(上述の移動行為によって)移動した場合,そのいたずらっ子はあなたを抱えて区画$(1,1)$に移動し,
そこにあなたを置いていったうえで公園の外にある自宅に帰ります.
なお,いたずらっ子はとても足が速いため,彼女があなたを抱えて区画$(1,1)$まで移動し,あなたを解放するまでにかかる時間は0分としてよいです.

$H\times W$個の区画の情報が入力より与えられます.
$a_{i,j}$が'.'ならば区画$(i,j)$は何もなく,'k'ならば区画$(i,j)$にはいたずらっ子が待ち構えています.

あなたが区画$(H,W)$にたどり着くためにかかる最短の時間を$x$分とします. $x$の値を出力してください.

入力

$H\ W\\
    a_{1,1}...a_{1,W}\\
    :\\
    a_{H,1}...a_{H,W}$

  • $1 \le H,W \le 2000$
  • $(H,W) \ne (1,1)$
  • $H,W$は整数
  • $a_{i,j} = $ '.'または$a_{i,j}=$ 'k'
  • $a_{1,1}\ne$ 'k'
  • $a_{H,W}\ne$ 'k'

出力

$x$の値を出力してください.
最後に改行してください.

サンプル

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

あなたはまず,(たとえば)区画$(1,1)$から区画$(2,1)$に1分かけて移動できますが,
直後にその区画で待ち構えているいたずらっ子によって区画$(1,1)$に戻されてしまいます.
そこから区画$(1,1)\rightarrow$区画$(2,1) \rightarrow $区画$(2,2)$という移動を行うと,合計3分で目的を達成できます.これが最短時間です.

サンプル2
入力
5 4
....
kk..
....
..kk
....
出力
8

サンプル3
入力
5 5
..kkk
k.kkk
k..kk
kk.kk
kk...
出力
8

サンプル4
入力
3 4
.kkk
k..k
kkk.
出力
10

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