题解#机器人的运动范围#

'''
解题思路：
将行坐标和列坐标的数位之和大于k的格子设为不可访问，即visited[i][j]=1，然后用BFS搜索
'''
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:

        Dic = {}
        for i in range(max(m,n)+1):
            t = sum(map(int,list(str(i))))
            Dic[i] = t
        #print(Dic)

        visited = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if Dic[i]+Dic[j]>k:
                    visited[i][j] = 1
        #print(visited)

        stack = [[0,0]]
        visited[0][0] = 1
        MV = [[0,1],[0,-1],[1,0],[-1,0]]
        res = 0
        while stack:
            xy = stack.pop()
            res += 1
            i = xy[0]
            j = xy[1]
            for mv in MV:
                ii = i+mv[0]
                jj = j+mv[1]
                if 0<=ii<=m-1 and 0<=jj<=n-1 and visited[ii][jj]==0:
                    visited[ii][jj] = 1
                    stack.insert(0,[ii,jj])
        #print(res)
        return res