class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
node_list = [(0, 0)]
checked_table = set()
while node_list:
(i, j) = node_list.pop()
if i >= n or j >= m or (i, j) in checked_table or sum(map(int, str(i)+str(j))) > k:
continue
checked_table.add((i, j))
for x, y in [(1, 0), (0, 1)]:
node_list.append((i+x, j+y))
return len(checked_table)
递归
把上边的 dfs 算法改成递归的写法试试：
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
checked_table = set()
def dfs(i, j):
nonlocal checked_table
if i >= n or j >= m or (i, j) in checked_table or sum(map(int, str(i)+str(j))) > k:
return
checked_table.add((i, j))
for x, y in [(1, 0), (0, 1)]:
dfs(i+x, j+y)
dfs(0, 0)
return len(checked_table)
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
visited = { (0, 0) }
for i in range(m):
for j in range(n):
if ((i-1, j) in visited or (i, j-1) in visited) and sum(map(int, str(i)+str(j))) <= k:
visited.add((i, j))
return len(visited)
leetcode 上有个「每日一题」，每天刷一下也挺有意思的。
https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
老实讲，看到这题后我是一点思路都没有。脑子里大概有一个小光标在右移、下移，移动的中间肯定会遇到一片阻挡过不去，然后停止移动，算下有多少个格子就行了。但就不知道如何写逻辑。
然后看了评论里的一个解答。里边提到了 bfs 和 dfs，我也是搜了一下才知道是广度优先搜索和深度优先搜索。
然后大概就理解了，关掉答案，试着凭借理解写出代码。
解法一：广度/深度优先搜索
首先有几个小问题需要解答：
先列出 3, 5, 3, 7 然后再 sum() 就行了。如何分别列出？
用一个列表推导式 (List Comprehensions)：
还有一种写法是用 map 函数，它将返回一个迭代器，其中每个元素都先 function() 一下：
因为是从 [0, 0] 开始搜索，方向一定是往右或往下。所以对于一个点，它的子节点就只有这两个方向。
对于一个节点，它可能之前判断过，所以如果判断过，就存下来不再操作（不再添加它的子节点）。
按照我的理解，这样的写法应该是「深度优先搜索」，因为 node_list.pop() 是每次把最近添加的子节点弹出来「搜」一下。
写完代码后，别急着运行或提交。先仔细地把代码读一遍，在脑子里边把逻辑都走一遍。会立马发现一些小错误。
小优化
上边的代码中的 checked_map 暴露了我对 python 的不熟悉。我的本意是用一个能快速判断某个元素在不在其中的元素。我本能的知道 dict 的 key 有这个功能。
但在这里不需要用 dict，因为用了它还得给每个 key 赋一个用不到的值（如
checked_map[(i, j)] = 1）。这里用 set 就可以了。还要注意 set 和 dict 初始化的区别：
往 set 中添加一个新的元素用它的 add() 方法。
还要注意，一个元组 tuple （如 (1, 2) ）可以作为 dict 的 key，或 set 的元素，因为元组是不可变的常量，可被 hash。
上边的代码改写一下，写得更 "python" 一点：
递归
把上边的 dfs 算法改成递归的写法试试：
解法二：递推
合法的格子 (i, j) 符合两个条件：
怎么判断一个格子是可达的呢？
从左往右、从上往下一个格子一个格子的计算，如果一个格子可达，那么它的左边格子或上边格子至少有一个是可达的。
想到这一层，就好办了。