再帰を用いた関数から返り値が返ってこない

※別途質問した内容と用いるコードは同じものですが、質問の内容が異なる為改めて質問を立てさせて頂きます。

#質問
深さ優先探索によって迷路のスタートからゴールまでの手順を調べる関数を作っていました。迷路リストは障壁が9, 未踏部分が0, ゴールが1, 既に踏んだ部分は2としています、参考にしている本では、以下のようなコードが示されています：

Python
1maze = [
2    [9, 9, 9, 9, 9, 9],
3    [9, 0, 0, 0, 0, 9],
4    [9, 0, 0, 0, 0, 9],
5    [9, 0, 0, 0, 0, 9],
6    [9, 0, 1, 0, 0, 9],
7    [9, 9, 9, 9, 9, 9]
8]
9
10
11def dfs(x, y, d):
12    if maze[x][y] == 1:
13        print(d)
14        exit()
15
16    maze[x][y] = 2
17
18    if maze[x - 1][y] < 2:
19        dfs(x - 1, y, d + 1)
20    if maze[x + 1][y] < 2:
21        dfs(x + 1, y, d + 1)
22    if maze[x][y - 1] < 2:
23        dfs(x, y - 1, d + 1)
24    if maze[x][y + 1] < 2:
25        dfs(x, y + 1, d + 1)
26
27    maze[x][y] = 0
28
29 
30dfs(1, 1, 0)

ここで、求められた返り値が必要になった為、

Python
1maze = [
2    [9, 9, 9, 9, 9, 9],
3    [9, 0, 0, 0, 0, 9],
4    [9, 0, 0, 0, 0, 9],
5    [9, 0, 0, 0, 0, 9],
6    [9, 0, 1, 0, 0, 9],
7    [9, 9, 9, 9, 9, 9]
8]
9
10
11def dfs(x, y, d):
12    if maze[x][y] == 1:
13        return d
14
15    maze[x][y] = 2
16
17    if maze[x - 1][y] < 2:
18        dfs(x - 1, y, d + 1)
19    if maze[x + 1][y] < 2:
20        dfs(x + 1, y, d + 1)
21    if maze[x][y - 1] < 2:
22        dfs(x, y - 1, d + 1)
23    if maze[x][y + 1] < 2:
24        dfs(x, y + 1, d + 1)
25
26    maze[x][y] = 0
27
28 
29depth = dfs(1, 1, 0)
30print(depth)

としたのですが、こうするとどのような迷路に対しても None が出力されます。
どのような理由で求められた値がprintをreturnにしただけでNoneになってしまったのでしょうか。おそらく大変初歩的な質問とは存じ上げますが、何卒ご教授のほどよろしくお願い申し上げます。

行動規範の内容に同意します

回答3件

python
1def dfs(x, y, d):
2    if maze[x][y] == 1:
3        return d
4
5    maze[x][y] = 2
6
7    if maze[x - 1][y] < 2:
8        dfs(x - 1, y, d + 1)
9    if maze[x + 1][y] < 2:
10        dfs(x + 1, y, d + 1)
11    if maze[x][y - 1] < 2:
12        dfs(x, y - 1, d + 1)
13    if maze[x][y + 1] < 2:
14        dfs(x, y + 1, d + 1)
15
16    maze[x][y] = 0

これをreturnに着目して読むと

「dfs(x, y, d)はmaze[x][y] == 1であればdを返し、そうでなければ何も返さない(None)」
です。

意図のようなコードはこちら

python
1# coding: utf-8
2# Your code here!
3
4maze = [
5[9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
6[9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9],
7[9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 9],
8[9, 9, 0, 0, 0, 0, 0, 0, 0, 9, 0, 9],
9[9, 9, 0, 0, 9, 9, 9, 9, 0, 9, 0, 9],
10[9, 9, 9, 0, 0, 0, 0, 9, 0, 9, 0, 9],
11[9, 9, 9, 9, 9, 9, 0, 9, 0, 9, 0, 9],
12[9, 1, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9],
13[9, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9],
14[9, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9],
15[9, 9, 0, 0, 0, 0, 0, 9, 0, 0, 0, 9],
16[9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
17]
18
19
20def dfs(x, y, d):
21    if maze[x][y] == 1:
22        return d
23        
24    maze[x][y] = 2
25
26    if maze[x - 1][y] < 2:
27        r = dfs(x - 1, y, d + 1)
28        if r is not None:
29            return r
30            
31    if maze[x + 1][y] < 2:
32        r = dfs(x + 1, y, d + 1)
33        if r is not None:
34            return r
35            
36    if maze[x][y - 1] < 2:
37        r = dfs(x, y - 1, d + 1)
38        if r is not None:
39            return r
40            
41    if maze[x][y + 1] < 2:
42        r = dfs(x, y + 1, d + 1)
43        if r is not None:
44            return r
45
46    maze[x][y] = 0
47    return None
48
49
50print(dfs(1, 1, 0))

投稿2021/07/13 02:05

編集2021/07/13 02:58

ozwk

総合スコア13528

kay_ventris4

2021/07/13 02:06

ご丁寧にありがとうございました。勉強になりました。

kay_ventris4

2021/07/13 02:43

たびたび申し訳ございません。ほとんどのケースではうまくいったのですが、 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9] [9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9] [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 9] [9, 9, 0, 0, 0, 0, 0, 0, 0, 9, 0, 9] [9, 9, 0, 0, 9, 9, 9, 9, 0, 9, 0, 9] [9, 9, 9, 0, 0, 0, 0, 9, 0, 9, 0, 9] [9, 9, 9, 9, 9, 9, 0, 9, 0, 9, 0, 9] [9, 1, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9] [9, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9] [9, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9] [9, 9, 0, 0, 0, 0, 0, 9, 0, 0, 0, 9] [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9] の迷路(スタートをmaze[1][1])で頂いたコードを実行したところ、本来は50と出力されるはずがNoneが出力されました。こちらはどのようなことが考えられますでしょうか。よろしくお願い申し上げます。