剑指offer-机器人的运动范围

本文为剑指 offer 系列第六十三篇。
主要知识点为二维数组的遍历和元素的处理，这个题目和前面的那个矩阵中的路径题目是类似的。

题目描述

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

解题思路

本题目和矩阵中寻找路径是类似的，
我们可以将这个题目要处理的数据范围抽象成为rows*cols的一个矩阵（或者第一象限），然后从一个结点开始出发，判断其四周的数据是不是合法的，类似于深度优先搜索对每个结点进行遍历。
同样的为了保证访问的数据不会重复，需要通过一个数组来保存每个数据之前是否已经被处理过。
这种处理方式比较经典，要多加锻炼。

解题代码

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        if(threshold <= 0 || rows <=0 || cols <= 0){
            return 0;
        }
        bool *flags = new bool[rows*cols];
        for(int i = 0; i < rows * cols; i++){
             flags[i] = false;
        }
        return helper(threshold,rows,cols,0,0,flags);
    }
    int helper(int threshold,int rows,int cols,int i,int j,bool *flags){
        int res = 0;
        if(checkToGo(threshold,rows,cols,i,j,flags)){
            flags[i*cols+j] = true;
            res = 1+helper(threshold,rows,cols,i+1,j,flags)
                +helper(threshold,rows,cols,i-1,j,flags)
                +helper(threshold,rows,cols,i,j+1,flags)
                +helper(threshold,rows,cols,i,j-1,flags);
        }
        return res;
    }
    bool checkToGo(int threshold,int rows,int cols,int i,int j,bool *flags){
        if(i>=0 && i<rows && j>=0 && j<cols && checkThreshold(threshold,i,j) && flags[i*cols+j] == false){
            return true;
        }
        return false;
    }
    bool checkThreshold(int threshold,int i,int j){
        int temp = 0;
        while(i){
            temp += i%10;
            i = i/10;
        }
        while(j){
            temp += j%10;
            j = j/10;
        }
        return temp<=threshold;
    }
    private:
        
};

时间复杂度为O(cols*rows*lg(max(rows,cols)),空间复杂度为O(cols*rows)
以上，本题结束！