こちらの問題に取り組んでいます。
再帰関数を用いた実装を試しているのですが、どうもうまくいきません。以下に私のコードを示します。
python
1import sys 2sys.setrecursionlimit(100000) 3 4H, W = map(int, input().split()) 5#mapを作る 6C = [] 7for _ in range(H): 8 c = input() 9 C.append([i for i in c]) 10 11print(C) 12#訪れたかどうかの記録 13reached = [[0] * W] * H 14 15def search(x, y): 16 print(reached) 17 #範囲外、塀、以前 訪れたところは何もしない 18 if x < 0 or x > W-1 or y < 0 or y > H - 1: 19 return 20 if C[y][x] == '#': 21 return 22 if reached[y][x]: 23 return 24 #まだ訪れてないところは訪れた印をつける 25 reached[y][x] = 1 26 27 search(x - 1, y) 28 search(x + 1, y) 29 search(x, y - 1) 30 search(x, y + 1) 31 32 33search(0, 0) 34 35#get index for 'g' and then see if the same index of reached is 1 36g = [g for g in C if 'g' in g][0] 37g_idx = (C.index(g), g.index('g')) 38 39#print(g_idx) 40#print(reached) 41if reached[g_idx[0]][g_idx[1]]: 42 print('Yes') 43else: 44 print('No') 45
確認のためところどころprintを入れてますが、
4 5 s#### ....# ##### #...g
を標準入力として受け取った時、出力は
[['s', '#', '#', '#', '#'], ['.', '.', '.', '.', '#'], ['#', '#', '#', '#', '#'], ['#', '.', '.', '.', 'g']] [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]] [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]] [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]] [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]] No
となり、どうも訪れたところの印付がうまくいっていないようなのですが、何度確認してもバグが見つけられません。
こちらはpythonによる同じ方針の実装です。
これと比較してもif...elseを使ってるかいないかぐらいの違いしか見つけられないのですが、何か勘違いしていますでしょうか?
なお入力に合わせて最初に関数を呼ぶ時の初期値を(0, 0)にしています。
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/03/23 08:35
2019/03/23 08:37
2019/03/23 08:41
2019/03/23 08:52 編集