1. paizaラーニングトップ
  2. レベルアップ問題集
  3. 幅優先探索・深さ優先探索メニュー(言語選択)
  4. 問題一覧
  5. ゴール判定

幅優先探索・深さ優先探索メニューのサムネイル
ゴール判定(paizaランク A 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

グリッドとスタート地点のマス (sy,sx), ゴール地点のマス (gy,gx) が与えられるので、スタート地点から次の操作を繰り返し、ゴール地点に到達することができるかを判定してください。

・現在いるマスを (y,x) としたとき、(y+1,x), (y-1,x), (y,x+1), (y,x-1) のいずれかのマスに移動する。

ただし、グリッドの外へは移動することができず、また、グリッド上の '#' のマスは壁であり、移動できないことに注意してください。
なお、グリッドの左上・右上・左下・右下のマスをそれぞれ (0,0), (0,W-1), (H-1,0), (H-1,W-1) とします。

入力される値

H W
sy sx
gy gx
S_1
...
S_H


・1 行目では、グリッドの行数 H , 列数 W が半角スペース区切りで与えられます。
・2 行目では、スタート地点のマスの座標を表す sy, sx が半角スペース区切りで与えられます。
・3 行目では、ゴール地点のマスの座標を表す gy, gx が半角スペース区切りで与えられます。
・続く H 行のうち i 行目 (1 ≦ i < H) には、グリッドの i-1 行目の文字をまとめた文字列 S_i が与えられ、S_i の j 文字目は、グリッドの i 行目の j-1 列目に書かれている文字を表します。(1 ≦ j < W)


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

・(sy,sx) から移動をして (gy,gx) に到達することができる場合は "Yes" を、到達できない場合は "No" を出力してください。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ H, W ≦ 100
・0 ≦ sy < H
・0 ≦ sx < W
・0 ≦ gy < H
・0 ≦ gx < W
・マス(sy,sx), (gy,gx) は '.' である
・ S_i は W 文字の文字列(1 ≦ i ≦ H)
・ S_i の各文字は '.' または '#'(1 ≦ i ≦ H)

入力例1

2 2
0 0
1 1
.#
#.

出力例1

No

入力例2

3 3
0 0
2 0
...
##.
...

出力例2

Yes

問題一覧へ戻る

ページの先頭へ戻る