No.2096 Rage With Our Friends
レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : 👑 AngrySadEight / テスター : chineristAC
タグ : / 解いたユーザー数 24
作問者 : 👑 AngrySadEight / テスター : chineristAC
問題文最終更新日: 2022-10-07 09:33:41
問題文
一人の少年が,2次元座標状のマップ上を旅しています.マップは 行 列の文字列 で与えられ, が .
であれば座標 に足場があることを, #
であれば座標 に足場がないことを表します.すべての に対し, .
です.
最初,少年は座標 にいます.少年の目標は,ゴールである座標 に行くことです.ここで, です.
少年は,エネルギー を持っており,はじめ です.少年は,次のような 種類の移動方法を用いることで,移動することができます.
- 通常ジャンプ:今いる座標を とする. を満たすような をひとつ選び, または に移動する.その後,少年の持つエネルギーは, に変化する.この移動は,移動先の座標に足場がある場合に限り行える.
- ブーストジャンプ:今いる座標を とする. を満たすような をひとつ選び, または に移動する.その後,少年の持つエネルギーは, に変化する.この移動は,移動先の座標に足場がある場合に限り行える.
ただし, を満たさないような座標 への移動を行うことはできません.
ブーストジャンプは難しい上に疲れるので,出来るだけその回数を少なくしたいと思っています.
少年がゴールに到達するのに必要なブーストジャンプの回数の最小値を求めてください.
入力
- は整数である.
- は
#
および.
からなる長さ の文字列である. -
.
-
.
出力
少年がゴールにたどり着ける場合,必要な最小のブーストジャンプの回数を出力せよ.たどり着けない場合は -1
を出力せよ.
サンプル
サンプル1
入力
4 6 1 1 4 6 ...... #.#### ##.### ###.#.
出力
1
次のようにすることで,ブーストジャンプ 回でゴールにたどり着けます.
- から,通常ジャンプを使用して に移動する. である.
- から,通常ジャンプを使用して に移動する. である.
- から,通常ジャンプを使用して に移動する. である.
- から,通常ジャンプを使用して に移動する. である.
- から,ブーストジャンプを使用して に移動する.
サンプル2
入力
3 3 1 2 3 2 ... ### ...
出力
-1
どうやってもゴールにたどり着くことはできません.
サンプル3
入力
5 2 1 1 5 1 .. .# .# .# .#
出力
3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。