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

剑指 Offer 13. 机器人的运动范围https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

首先实用小知识就是类似于a,b=3,4 

当后面数字是列表或元组时也可以

a,b=[1,2],a,b=(1,2)

此时相当于a=1,b=2的赋值操作。

第一种发方法，dfs

第二种方法，bfs

BFS/DFS ： 两者目标都是遍历整个矩阵，不同点在于搜索顺序不同。DFS 是朝一个方向走到底，再回退，以此类推；BFS 则是按照“平推”的方式向前搜索。
BFS 实现： 通常利用队列实现广度优先遍历。
算法解析：
初始化： 将机器人初始点 (0, 0) 加入队列 queue ；
迭代终止条件： queue 为空。代表已遍历完所有可达解。
迭代工作：
单元格出队： 将队首单元格的 索引弹出，作为当前搜索单元格。
判断是否跳过： 若 ① 行列索引越界 或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过 时，执行 continue 。
标记当前单元格 ：将单元格索引 (i, j) 存入 集合 visited 中，代表此单元格 已被访问过 。
单元格入队： 将当前元素的 下方、右方 单元格的 索引加入 queue 。
返回值： 集合visited 的长度 len(visited) ，即可达解的数量。

'''
#学到的以前没注意的知识点
lst=[[1,2],(3,4)]
i,j=lst[0]
m,n=lst[1]
print(i,j,m,n)
'''
'''
class Solution:
    def movingCount(self, m, n, k):
        def he(n1,n2):#求数位和
            val=0
            while(n1 or n2):
                val+=n1%10+n2%10
                n1=n1//10#向下取整
                n2=n2//10
            return val
        def dfs(i,j):
            res=he(i,j)
            if i>=m or j>=n or k<res or (i,j) in visited:return 0
            visited.add((i,j))
            return 1+dfs(i+1,j)+dfs(i,j+1)
        visited=set()
        return dfs(0,0)
'''
class Solution:
    def movingCount(self, m, n, k):
        def he(n1, n2):  # 求数位和
            val = 0
            while (n1 or n2):
                val += n1 % 10 + n2 % 10
                n1 = n1 // 10  # 向下取整
                n2 = n2 // 10
            return val
        queue,visited=[[0,0]], set()#队列可以用列表表示，弹出列表第一个就ok
        while queue:
            i,j=queue.pop(0)#弹出队首元素
#易出错的点，集合里放的是不可变对象,所以不可以些[i,j] in visited
            res=he(i,j)
            if i >= m or j >= n or k < res or (i, j) in visited:
                continue
            else:
                visited.add((i,j))
                queue.append([i+1,j])
                queue.append([i, j+1])
        return len(visited)

a=Solution()
print(a.movingCount(2,3,1))
print(a.movingCount(3,1,0))