面试题13：机器人的运动范围

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

知识点

递归，回溯法

Qiang的思路

这道题和面试题12（https://www.jianshu.com/p/223fe4484457）类似。但是在面试题12中，如果探索完一条路径之后，在探索下一条路径时之前做的标记都应该删除，不能相互影响。而这个题中，如果一个点已经走过了，那么其可以达到的点都应该走过，所以一个点仅仅需要走一次就可以了，也就是说多次探索之间公用一个标记矩阵，相互之间是需要信息共享的。

在解答时，我们首先需要对标记矩阵做一下预处理，将那些不能达到的地方统一标注为-1，这样在探索时只要遇到-1就不在继续探索。当然，对于探索过的区域标记为1，当遇到标记为1的地方说明之前已经探索过了，也不需要继续进行探索了。总而言之，我们只需要看一下下一步的位置是不是标记为0，只要当标记为0时我们采取探索。

# -*- coding:utf-8 -*-
class Solution:
    def getFlag(self, i, j, threshold):
        num=0
        while i!=0:
            num+=i%10
            i=int(i/10)
        while j!=0:
            num+=j%10
            j=int(j/10)
        if num>threshold:
            return -1
        else:
            return 0
        
    def getResult(self, i, j, rows, cols, flag):
        flag[i][j]=1
        if i>=1 and flag[i-1][j]==0:
            self.getResult(i-1, j, rows, cols, flag)
        if i<=rows-2 and flag[i+1][j]==0:
            self.getResult(i+1, j, rows, cols, flag)
        if j>=1 and flag[i][j-1]==0:
            self.getResult(i, j-1, rows, cols, flag)
        if j<=cols-2 and flag[i][j+1]==0:
            self.getResult(i, j+1, rows, cols, flag)
        
    def movingCount(self, threshold, rows, cols):
        # write code here
        flag=[[self.getFlag(i, j, threshold) for j in range(cols)] for i in range(rows)]
        if flag[0][0]==0:
            self.getResult(0, 0, rows, cols, flag)
        count=0
        for i in range(rows):
            for j in range(cols):
                if flag[i][j]==1:
                    count+=1 
        return count

一般来说，对于在二维数组中移动的问题使用回溯法可以解决。

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。