nouken score 351
2019/03/23 17:26 投稿
| python、深さ優先探索、再帰関数による実装 |
| [こちらの問題](https://atc001.contest.atcoder.jp/tasks/dfs_a)に取り組んでいます。 |
| 再帰関数を用いた実装を試しているのですが、どうもうまくいきません。以下に私のコードを示します。 |
| ```python |
| import sys |
| sys.setrecursionlimit(100000) |
| H, W = map(int, input().split()) |
| #mapを作る |
| C = [] |
| for _ in range(H): |
| c = input() |
| C.append([i for i in c]) |
| print(C) |
| #訪れたかどうかの記録 |
| reached = [[0] * W] * H |
| def search(x, y): |
| print(reached) |
| #範囲外、塀、以前 訪れたところは何もしない |
| if x < 0 or x > W-1 or y < 0 or y > H - 1: |
| return |
| if C[y][x] == '#': |
| return |
| if reached[y][x]: |
| return |
| #まだ訪れてないところは訪れた印をつける |
| reached[y][x] = 1 |
| search(x - 1, y) |
| search(x + 1, y) |
| search(x, y - 1) |
| search(x, y + 1) |
| search(0, 0) |
| #get index for 'g' and then see if the same index of reached is 1 |
| g = [g for g in C if 'g' in g][0] |
| g_idx = (C.index(g), g.index('g')) |
| #print(g_idx) |
| #print(reached) |
| if reached[g_idx[0]][g_idx[1]]: |
| print('Yes') |
| else: |
| print('No') |
| ``` |
| 確認のためところどころ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による同じ方針の実装です。](https://atc001.contest.atcoder.jp/submissions/2709491) |
| これと比較してもif...elseを使ってるかいないかぐらいの違いしか見つけられないのですが、何か勘違いしていますでしょうか？ |
| これと比較してもif...elseを使ってるかいないかぐらいの違いしか見つけられないのですが、何か勘違いしていますでしょうか？ |
| なお入力に合わせて最初に関数を呼ぶ時の初期値を（0, 0)にしています。 |
