|
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3
示例 2：
输入：m = 3, n = 1, k = 0
输出：1
提示：
1 <= n,m <= 100
0 <= k <= 20
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
目录
思路1：深搜（dfs）
思路2：广搜（bfs）
思路3：递推
思路1：深搜（dfs）
从起点（0，0）开始朝四个方向搜索，能够继续的条件就是坐标的位数和不大于K.
传统的深搜是四个方向的，但是本题可以优化为：向右和向下。
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
# 暴力
self.cnt = 0
self.n = n
self.m = m
self.k = k
self.visit = [[0]*n for _ in range(m)]
self.dx = [0, 1] # 优化为只：向右、向下
self.dy = [1, 0]
self.visit[0][0] = 1
self.dfs(0, 0)
return self.cnt
def dfs(self, x, y):
ti = x
tj = y
t = 0
while ti > 0:
t += ti % 10
ti = ti // 10
while tj > 0:
t += tj % 10
tj = tj // 10
if t <= self.k:
self.cnt += 1
else:
return
for i in range(2):
xx = x + self.dx[i]
yy = y + self.dy[i]
if 0 <= xx < self.m and 0 <= yy < self.n and self.visit[xx][yy] == 0:
self.visit[xx][yy] = 1
self.dfs(xx, yy)
思路2：广搜（bfs）
广搜是利用一个队列实现的，且本题利用set进行去重。
def digitsum(n):
ans = 0
while n:
ans += n % 10
n //= 10
return ans
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
from queue import Queue
q = Queue()
q.put((0, 0))
s = set()
while not q.empty():
x, y = q.get()
if (x, y) not in s and 0 <= x < m and 0 <= y < n and digitsum(x) + digitsum(y) <= k:
s.add((x, y))
q.put((x, y + 1))
q.put((x + 1, y))
return len(s)
思路3：递推
def digitsum(n):
ans = 0
while n:
ans += n % 10
n //= 10
return ans
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
s = set([(0, 0)])
for i in range(m):
for j in range(n):
if ((i-1,j) in s or (i,j-1) in s) and digitsum(i) + digitsum(j) <= k:
s.add((i, j))
return len(s)
| 
转播
