問題一覧 > ネタ問題

No.3063 幅優先探索

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 125
作問者 : googol_S0googol_S0
8 ProblemId : 4103 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-03-19 20:09:17

問題文

たかはし君は迷路が好きです。今、上下左右に移動できる二次元盤面上の迷路を解こうとしています。盤面は以下のような形式で与えられます。
・まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
・次に、それぞれのマスが空きマス(.)か壁マス(#)かという情報を持った盤面が与えられる。スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは必ずたどり着ける。
この迷路でスタートからゴールまで移動するための最小移動回数を出力しなさい。ただし、斜めには移動できません。

入力

$R\ C$
$sy\ sx$
$gy\ gx$
$c_{(1,1)}\ c_{(1,2)}\ ...\ c_{(1,C)}$
$c_{(2,1)}\ c_{(2,2)}\ ...\ c_{(2,C)}$
$.$
$.$
$.$
$c_{(R,1)}\ c_{(R,2)}\ ...\ c_{(R,C)}$

$R,C$はそれぞれ行の数と列の数
$sy,sx$はスタート地点の座標 $sy$がy座標,$sx$がx座標
$gy,gx$はゴール地点の座標 $gy$がy座標,$gx$がx座標
$c_{(i,j)}$は$(i,j)$が空きマスであるか壁マスであるかを示す '.'なら空きマス '#'なら壁マス
$1\leq R,C \leq10^3$
$1\leq sy,gy \leq R$
$1\leq sx,gx \leq C$

出力

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

サンプル

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

サンプル2
入力
10 10
2 2
9 9
##########
#........#
#.######.#
#.######.#
#.######.#
#.######.#
#.######.#
#.######.#
#........#
##########
出力
14

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