剑指 Offer 13. 机器人的运动范围
链接：
https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
典型的用dfs或者bfs的题目，另外还有一种dp的方式，因为这里的坐标都是递增的，所以可以简化的只考虑值向右或者向下移动即可。
bfs：注意python中计算数的每个位之和的方式，还有用set来判断当前位置是否被访问过
我要评论
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
def f(num):
return sum(int(i) for i in str(num))
dx = [0, 1]
dy = [1, 0]
ans = 1
queue, vis = [], set()
queue.append((0, 0))
vis.add((0, 0))
while queue:
x, y = queue.pop(0)
for i in range(len(dx)):
tx = x + dx[i]
ty = y + dy[i]
if tx < 0 or tx >= m or ty < 0 or ty >= n or f(tx)+f(ty)>k or (tx, ty) in vis:
continue
ans += 1
queue.append((tx, ty))
vis.add((tx, ty))
return ans
dfs的做法
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
def f(num):
return sum(int(i) for i in str(num))
def dfs(x, y):
if x < 0 or x >= m or y < 0 or y >= n or f(x)+f(y)>k or (x, y) in vis:
return 0
vis.add((x, y))
dfs(x+1, y)
dfs(x, y+1)
vis = set()
dfs(0, 0)
return len(vis)
递推：如果(i,j)是满足要求的，只要(i-1,j)或者(i,j-1)是可达的就证明(i,j)也是可达的
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
def f(num):
return sum(int(i) for i in str(num))
vis = [[0 for j in range(n)] for i in range(m)]
vis[0][0] = 1
ans = 1
for i in range(m):
for j in range(n):
if (i == 0 and j == 0) or f(i)+f(j)>k:
continue
if (i-1) >= 0:
vis[i][j] = vis[i][j] | vis[i-1][j]
if (j-1) >= 0:
vis[i][j] = vis[i][j] | vis[i][j-1]
ans += vis[i][j]
return ans
本文地址：https://blog.csdn.net/breeze_blows/article/details/107645452
如对本文有疑问， 点击进行留言回复！！
网友评论