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

幅優先探索・深さ優先探索メニューのサムネイル
グリッドの深さ優先探索(3 マス)(paizaランク A 相当)

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

問題

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

ここから先は深さ優先探索の問題を扱います。
深さ優先探索とは、移動することが不可能になるまで移動を繰り返した先の頂点を訪問し、
その後 1 つ前の頂点に戻るような操作を、移動できなくなるまで繰り返す探索のことです。

グリッドの行数 H と列数 W とマス (y,x) が与えられるので、深さ優先探索で 3 マス移動した後にいるマスの座標を順に出力してください。
移動の途中で端にぶつかった場合は、出力をせずにその移動を打ち切ってください。
なお、探索の際の移動は上,右,下,左の順におこなうものとし、グリッドの左上・右上・左下・右下のマスをそれぞれ (0,0), (0,W-1), (H-1,0), (H-1,W-1) とします。

例として、次の図のような入力について深さ優先探索の流れを紹介します。
赤いマスがスタート地点とします。
幅優先探索であれば、スタート地点から 1,2,3,4 の順にマスを訪問しますが、深さ優先探索は移動できなくなるまで 1 の方向に進み続けて、進めなくなったとき初めて 2,3,4 といった順にマスを訪問します。



図1




そのため、図 1 の状態から図 2, 3 のように進んでいき、図 3 の状態から 1 の方向に移動したところで、移動したマス数が合計で 3 になり、初めて 2 の方向に移動します。
そのため、訪問したマスの順番は図 4 の通りになります。


図2





図3





図4




図 3 の状態から可能な移動を全てしたため、次は図 2 の 2 の方向に移動して図 5 の通り移動を行います。このような移動を繰り返し、深さ優先探索は、全ての 3 マスの移動、もしくは壁にぶつかる移動を探索します。



図5


入力される値

H W y x


・1 行で、グリッドの行数 H , 列数 W, スタート地点の座標を表す y, x が半角スペース区切りで与えられます。


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

・(y,x) から深さ優先探索順に 3 マス移動をした後にいるマスの座標 y, x を訪問順に改行区切りで出力してください。

条件

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

・1 ≦ H, W ≦ 100
・0 ≦ y < H
・0 ≦ x < W

入力例1

7 7 3 3

出力例1

0 3
1 4
2 3
1 2
1 4
2 5
3 4
2 3
2 3
3 4
4 3
3 2
1 2
2 3
3 2
2 1
1 4
2 5
3 4
2 3
2 5
3 6
4 5
3 4
3 4
4 5
5 4
4 3
2 3
3 4
4 3
3 2
2 3
3 4
4 3
3 2
3 4
4 5
5 4
4 3
4 3
5 4
6 3
5 2
3 2
4 3
5 2
4 1
1 2
2 3
3 2
2 1
2 3
3 4
4 3
3 2
3 2
4 3
5 2
4 1
2 1
3 2
4 1
3 0

入力例2

2 2 0 0

出力例2

0 1
1 0
0 1
1 0
0 1
1 0
0 1
1 0

問題一覧へ戻る

ページの先頭へ戻る