こんにちはSoheiです
今回は幅優先探索と深さ優先探索の練習問題であるAOJ-1130 Red and blackという問題を解いていきたいと思います！
流れ
①迷路を読み込む
②@地点をqueue(stack)の中に入れる
③タイルの地点を取り出す
④近いタイルが”.”だった場合そのタイルの地点をqueue(stack)に入れる
⑤④で入れたタイルを”＄”とし、カウントを一つ増やす
⑥終わりか判定
⑦③に戻る
⑧最後にカウントを出力
実装
幅優先
sohei.py
while 1:
w,h = map(int, raw_input().split())
if w == h == 0:
break
count = 0
cnt = 1
lst = [list(raw_input()) for i in range(h)]
queue = []
for i in range(h):
if "@" in lst[i]:
wNow, hNow = lst[i].index("@"),i
queue.append([hNow, wNow])
while 1:
hNow,wNow = queue[0][0],queue[0][1]
queue.pop(0)
if hNow < h-1:
if lst[hNow+1][wNow] == ".":
queue.append([hNow+1,wNow])
lst[hNow+1][wNow] = "$"
cnt += 1
if wNow < w-1:
if lst[hNow][wNow+1] == ".":
queue.append([hNow,wNow+1])
lst[hNow][wNow+1] = "$"
cnt += 1
if hNow > 0:
if lst[hNow-1][wNow] == ".":
queue.append([hNow-1,wNow])
lst[hNow-1][wNow] = "$"
cnt += 1
if wNow > 0:
if lst[hNow][wNow-1] == ".":
queue.append([hNow,wNow-1])
lst[hNow][wNow-1] = "$"
cnt += 1
if len(queue) == 0:
break
print cnt
深さ優先
hello.py
while 1:
w,h = map(int, raw_input().split())
if w == h == 0:
break
count = 0
cnt = 1
lst = [list(raw_input()) for i in range(h)]
Stack = []
for i in range(h):
if "@" in lst[i]:
wNow, hNow = lst[i].index("@"),i
Stack.append([hNow, wNow])
while 1:
hNow,wNow = Stack[-1][0],Stack[-1][1]
Stack.pop(-1)
if hNow < h-1:
if lst[hNow+1][wNow] == ".":
Stack.append([hNow+1,wNow])
lst[hNow+1][wNow] = "$"
cnt += 1
if wNow < w-1:
if lst[hNow][wNow+1] == ".":
Stack.append([hNow,wNow+1])
lst[hNow][wNow+1] = "$"
cnt += 1
if hNow > 0:
if lst[hNow-1][wNow] == ".":
Stack.append([hNow-1,wNow])
lst[hNow-1][wNow] = "$"
cnt += 1
if wNow > 0:
if lst[hNow][wNow-1] == ".":
Stack.append([hNow,wNow-1])
lst[hNow][wNow-1] = "$"
cnt += 1
if len(Stack) == 0:
break
print cnt
では実際に動かしてみたいと思います。
#Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
#Output
45
ちゃんと出力してくれました
学んだ知識
・list内包表記について
考察
今回の学習で、深さ優先と幅優先の違いのようなものを感じました。今の例では迷路を考えていますが、迷路の種類によっては深さ優先の方が有利な時もありますが、迷路が膨大な場合を考えると、猪突猛進な深さ優先は解を求めるのに時間がかかる場合がある。それに比べて、幅優先の解を見つける速度は、言うまでもなく速いです、ですが、深さ優先は迷路が膨大な時、まれに解にたどり着ける場合があります。例えるなら幅優先が真面目な生徒会長という感じで、深さ優先は映画の主人公の勇者といった感じでしょうか。なので実用例にも違いがあります。例えば幅優先は、マップの経路などに向いていると思います。最短距離を正確に出してくれます。深さ優先は、幅優先で地道にやっていては解が見つからないようなパズルなどに向いていると思います。
今後、アルゴリズムと関わっていく中で、この幅優先と深さ優先の使い分けに気をつけていきたいと思いました。
今回はこれで失礼します
次回は新しいアルゴリズムに挑戦してみようかなと思っております。
それではメリークリスマス！！