質問編集履歴

1 情報追加

nouken

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)にしています。
  • Python

    34462 questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

思考するエンジニアのためのQ&Aサイト「teratail」について詳しく知る