実現したいこと
PythonにてDFS(再帰)を用いて、特定の条件を満たすルートを全て洗い出したいです。
前提
Atcoder で以下の問題をDFS(再帰)を用いて解きたいと考えています。
https://atcoder.jp/contests/abc293/tasks/abc293_c
発生している問題・エラーメッセージ
下に自分の書いたコードを添付します。
17行目で”ゴールに辿り着いた際、一段階戻って他の経路の探索を続ける”ことができないです。
ですが、returnを取り外すと継続できます。
また13行目で行っている、”条件に合わなかった場合、一段階戻って他の経路の探索を続ける”についてはreturnがついていても可能です。
これはなぜなのでしょうか。
returnにはどのようなルールがあるのか理解できずにいます。
該当のソースコード
python
1import sys 2 3sys.setrecursionlimit(10**7) 4 5H, W = map(int, input().split()) 6 7masu = [tuple(map(int, input().split())) for _ in range(H)] 8 9check = set() 10cnt = 0 11 12def dfs(x,y): 13 if masu[y][x] in check: 14 #print(check) 15 return 16 check.add(masu[y][x]) 17 if x == W-1 and y == H-1: 18 #print("flag") 19 global cnt 20 cnt += 1 21 return 22 23 if x < W-1: 24 dfs(x+1, y) 25 if y < H-1: 26 dfs(x, y+1) 27 28 check.remove(masu[y][x]) 29 30dfs(0,0) 31
試したこと
再帰の深さの遍歴を確認しました。
returnをつけてもゴールには規定回数(3回)たどり着けているようですが、カウントが1回だけになっているようで、ここに原因があるようですが理由まではわかりませんでした。。。
python
1import sys 2 3sys.setrecursionlimit(10**7) 4 5H, W = map(int, input().split()) 6 7masu = [tuple(map(int, input().split())) for _ in range(H)] 8 9check = set() 10cnt = 0 11depth = 0 12def dfs(x,y, depth): 13 depth += 1 14 print(depth) 15 global cnt 16 if masu[y][x] in check: 17 #print(check) 18 cnt += 0 19 return 20 check.add(masu[y][x]) 21 22 if x == W-1 and y == H-1: 23 #print("flag") 24 cnt += 1 25 return 26 27 if x < W-1: 28 dfs(x+1, y, depth) 29 if y < H-1: 30 dfs(x, y+1, depth) 31 32 check.remove(masu[y][x]) 33 34dfs(0,0,0) 35 36#print(cnt) 37
3 3 3 2 2 2 1 3 1 5 4
1 2 3 3 4 4 5 2 3 4 4 5 3 4 5
試行したことを追記しました。

回答1件
あなたの回答
tips
プレビュー