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

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

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

問題

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

グリッドが与えられるので、マス (y,x) から次の操作を 1 回としたとき、N 回以内に到達することができるマスを '*' , それ以外のマスを '.' にしたグリッドを出力してください。

・現在いるマスを (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) とします。

--- ヒント ---
基本的な移動の仕組みは 1 つ前の問題の「N マスの移動」で扱った幅優先探索と同じなので、そのコードに
「移動先が壁でない場合にのみ移動を行う」という条件判定を加えましょう。

入力される値

H W N
y x
S_1
...
S_H


・1 行目では、グリッドの行数 H , 列数 W, 移動する回数 N が半角スペース区切りで与えられます。
・2 行目では、移動を開始するマスの座標を表す y, x が半角スペース区切りで与えられます。
・続く H 行のうち i 行目 (1 ≦ i ≦ H) には、グリッドの i-1 行目の文字をまとめた文字列 S_i が与えられ、S_i の j 文字目は、グリッドの i-1 行目の j-1 列目に書かれている文字を表します。(1 ≦ j ≦ W)


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

H 行の出力

・マス (y,x) から前後左右に N マス移動して到達することができるマスを '*' , それ以外のマスを '.' にしたグリッドを出力してください。
・各行の要素を繋げて文字列としたものを改行区切りで出力してください。
・詳しくは入力例を参考にしてください。

条件

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

・1 ≦ H, W ≦ 10
・0 ≦ N ≦ 10
・0 ≦ y < H
・0 ≦ x < W
・ S_i は W 文字の文字列(1 ≦ i ≦ H)
・ S_i の各文字は '.' または '#'(1 ≦ i ≦ H)
・マス (y,x) の文字は '.'

入力例1

7 10 9
5 2
#...#.....
.###...#.#
#..#....##
.#.###..##
##.....###
##.##....#
#..#.##..#

出力例1

#...#.*...
.###.**#.#
#**#****##
.#*###**##
##*****###
##*##****#
#**#.##**#

入力例2

9 6 8
5 0
....##
.#.##.
#...##
#.####
#.##.#
.###.#
..####
#...##
#.###.

出力例2

....##
.#.##.
#...##
#.####
#.##.#
*###.#
**####
#***##
#*###.

問題一覧へ戻る

ページの先頭へ戻る