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

题目：机器人的运动范围

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

范围: 1 <= rows, cols<= 100，0 <= threshold <= 20

示例1：输入：1,2,3，返回值：3

解法一：

        思路分析：我们可以使用递归法进行判断，因为题目中有要求，首先保证机器人不能进入行坐标和列坐标的数位之和大于threshole的格子，如果发现大于，则将值进行返回，从上一次的位置再向其他位置进行递归，同时使用布尔值矩阵去判断是否进入，其次机器人走的格子超出了棋盘的范围，即进入的行列数大于最大的行列数，或者小于0则不符合条件，我们在回退的过程中不需要对标志或者计数进行清除。

        实例分析：输入：2，5，5，其中threshole为2，行为5，列为5。

        机器人每到一个位置，判断该位置是否有效，如果有效（满足三个条件），往左右上下移动，重复上述行为，最终遍历的范围就是运动的范围。通过程序运行最终返回结果值为6。

具体C++代码如下所示：

class Solution {
public:
    //提取数的每一位的和 
int getDigitalSum(int num)
{
    int sum = 0;
    while(num){
        sum += num%10;
        num = num/10;
    }
    return sum;
}
int movingCountCore(int threshold,int rows,int cols,int row,int col,bool *visited){
    if((threshold < (getDigitalSum(row)+getDigitalSum(col)))||(row >= rows)||(col >= cols)||(row < 0)||(col < 0)||(visited[row*cols+col]))
        return 0;
    //满足所有访问条件，说明机器人可以进入该格子。
    int resu = 1;
    visited[row*cols+col] = true;  
    //当前格子的四周进行查看
    resu = resu + movingCountCore(threshold,rows,cols,row+1,col,visited)
            + movingCountCore(threshold,rows,cols,row,col+1,visited)
            + movingCountCore(threshold,rows,cols,row-1,col,visited)
            + movingCountCore(threshold,rows,cols,row,col-1,visited);
    return resu;
}
 
int movingCount(int threshold, int rows, int cols){                
    //输入不满足条件时，行列小于等于0的情况，返回0
    if((threshold < 0)||(rows <=0)||(cols <= 0))return 0;
    //建立一个同样大小的bool矩阵用于记录是否已经判断过
    bool *visited = (bool *)malloc(rows*cols);
    memset(visited,false,rows*cols);
    int resu = 0;
    resu = movingCountCore(threshold,rows,cols,0,0,visited);
    //记得释放分配的内存空间
    free(visited);
    return resu;
}
};

其中时间复杂度为O(MN)，MN为矩阵的大小，矩阵中的元素最多访问一次。空间复杂度为O(MN)，因为要申请一片连续的内存空间。

解法二：

思路分析：我们使用暴力循环的方法，判断该坐标内的每一个元素是否符合上述三个条件，如果符合条件，就将count++，否则，不予理会，用visited判断记录下一个可以进入的结点。

具体Java代码如下所示：

public class Solution {
    public int movingCount(int k, int m, int n) {
        int count = 0;//表示次数
        boolean[][] visited = new boolean[m][n];//新建visited对象
        visited[0][0] = true;//第一个值肯定为真
        for(int i =0; i<m; i++){//循环判断
            for(int j =0; j<n; j++){
                if(compareKey(i, j, k) && visited[i][j]){
                    if(i+1 < m)
                        visited[i+1][j] = true;
                    if(j+1 < n)
                        visited[i][j+1] = true;
                    count++;
                }
            }
        }
        return count;
    }
    
   /**
    *判断值是否符合
    **/
   public boolean compareKey(int i, int j, int k){
        int sum = sumNum(i) + sumNum(j);
        if(sum > k){
            return false;
        }
        return true;
    }
 
     /**
      *整数num的各位值之和
      **/
    public int sumNum(int num){
        int sum = 0;
        while(num > 0){
            sum = sum + num % 10;
            num = num / 10;
        }
        return sum;
   }
}

因为要将每行每列都进行判断，所以时间复杂度为O(N^2)。空间复杂度为O(1)。