剑指 Offer 13. 机器人的运动范围

 剑指 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