题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路
BFS
class Solution(object):
def movingCount(self, m, n, k):
"""
:type m: int
:type n: int
:type k: int
:rtype: int
"""
rows = m
cols = n
threshold = k
array = []
for i in range(rows):
res = []
for j in range(cols):
res.append(getN(i, j))
array.append(res)
visited = [[0] * len(array[0]) for _ in range(len(array))]
return BFS(array, 0, 0, threshold, visited)
def getN(i, j):
res = 0
while i:
res += (i % 10)
i //= 10
while j:
res += (j % 10)
j //= 10
return res
def BFS(array, i, j, threshold, visited):
if i<0 or j<0 or i>len(array)-1 or j>len(array[0])-1 or array[i][j]>threshold or visited[i][j]:
return 0
res = 1
visited[i][j] = 1
res += BFS(array, i+1, j, threshold, visited)
res += BFS(array, i-1, j, threshold, visited)
res += BFS(array, i, j+1, threshold, visited)
res += BFS(array, i, j-1, threshold, visited)
return res