欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-03 10:01:48
剑指 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(se......

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

链接:

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

 

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

 典型的用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