24.机器人的运动范围
题目描述:
地上有一个 m 行和 n 列的方格,横纵坐标范围分别是 0∼m−1 和 0∼n−1。
一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
请问该机器人能够达到多少个格子?
样例:
输入:k=18, m=40, n=40
输出:1484
解释:当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。
但是,它不能进入方格(35,38),因为3+5+3+8 = 19。
注意:
0<=m<=50
0<=n<=50
0<=k<=100
思路:
用宽度优先搜索,用一个队列来存储将要走的方格,队列存放的是每个放个的坐标。首先将起点(0, 0)添加到队列中,每次从队列头取一个格子,若该格子满足以下条件:
1.不超出格子的坐标,即$0\le x\le m-1 , 0\le y\le n-1 $
2.该格子还未走过——可以用一个m行n列的布尔矩阵来标记是否走过该格子,初始化为False,若该格子走过,设为True
3.该格子的横坐标和列坐标的数位之和不大于 k
则让res+=1,然后将该格子上下左右的四个格子加入到队列中
代码如下:
from collections import deque
class Solution(object):
def getSum(self, x, y):
sum = 0
sum += x // 10
sum += x % 10
sum += y // 10
sum += y % 10
return sum
def movingCount(self, threshold, rows, cols):
"""
:type threshold: int
:type rows: int
:type cols: int
:rtype: int
"""
queue = deque()
queue.append((0,0))
st = [[False] * cols for _ in range(rows)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
res = 0
while queue:
x, y = queue.popleft()
if x >=0 and x < rows and y >=0 and y <cols and not st[x][y] and self.getSum(x, y) <= threshold:
res += 1
st[x][y] = True
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
queue.append((nx, ny))
return res