【LeetCode】【剑指offer】【机器人的运动范围】

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

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

示例 1：

输入：m = 2, n = 3, k = 1
输出：3
示例 2：

输入：m = 3, n = 1, k = 0
输出：1
提示：

1 <= n,m <= 100
0 <= k <= 20

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

深度优先遍历。这里我们的思路就是从一个结点出发（0,0），然后递归遍历其右边的结点和下面的结点，也就是向着右下方遍历。

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vectorbool>> recorded(m,vector<bool>(n,0));
        return move(0,0,0,0,recorded,m,n,k);
    }
    //i表示的是当前我们访问的是第几行
    //j表示的是当前我们访问的是第几列
    //cout_i是用来计算i的数位和的
    //cout_j是用来计算j的数位和的
    //recorded是用来标记我们的结点是否被访问过的
    //m,n是我们题目中描述的m行n列的方格
    //k表示的是题目中没的航坐标和列坐标的数位之和不能大于k
    int move(int i,int j,int count_i,int count_j, vectorbool>> &recorded,int m,int n,int k)
    {
        //如果当前结点已经越界了，或者当前结点的行列和相加已经超出我们的k了
        //或者我们当前的结点被记录过已经访问过了
        //就表名当前结点已经不满足题目的要求了，不可以移动了，我们就直接返回0
        //注意下面的m,n,判断条件等号要取到
        
        if(i>=m||j>=n||count_i+count_j>k||recorded[i][j]==true)
        {
            return 0;
        }
        //标记我们的当前结点已经被访问过了
        recorded[i][j]=true;
        //向下遍历
        //向下遍历就是将我们的i坐标+1，但是相加之后我们需要判断新的i值的数位相加的结果的变化
        int new_count_i=0;
        if((i+1)%10==0)
        {
            //打个比方19的两位数相加原本是10，加一之后就变成了20，两位数相加的结果是2，也就是减小了8
            new_count_i=count_i-8;
        }
        else
        {
            //如果没有发生进位的话就直接+1
            new_count_i=count_i+1;
        }
        //向下递归遍历，取得先下右方向的符合要求的结点个数
        int right=move(i+1,j,new_count_i,count_j,recorded,m,n,k);
 
        //向右遍历
        //向右遍历就是将我们的j++
        //但是j++之后我们需要和之前一样判断我们的数位和的变化
        int new_count_j=0;
        if((j+1)%10==0)
        {
            new_count_j=count_j-8;
        }
        else
        {
            new_count_j=count_j+1;
        }
        //先向右遍历，取得向右遍历的所有符合条件的结点个数
        int down=move(i,j+1,count_i,new_count_j,recorded,m,n,k);
        //返回向右遍历和向下遍历的结果和
        //不要忘了当前结点也是一个符合要求的结点，需要+1
        return 1+right+down;
    }
};

或者采用广度优先遍历的方法

就是用一个队列存储我们的当前结点的相关数据，然后每一次都从队列的队首取出新的结点的信息，然后判断当前结点是否符合要求，符合要求的话就将我们的计数变量++，同时再将我们的当前结点右边结点的相关参数和当前几点下面的结点的相关参数压入我们的队列中。

这与我们的二叉树层序遍历非常类似。

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vectorbool>> recorded(m,vector<bool>(n,0));
        int result=0;
        //创建一个每一个元素都是容器的队列
        queueint>> tmp;
        //i表示的是当前我们访问的是第几行
        //j表示的是当前我们访问的是第几列
        //count_i是用来计算i的数位和的
        //count_j是用来计算j的数位和的
        //recorded是用来标记我们的结点是否被访问过的
        //m,n是我们题目中描述的m行n列的方格
        //k表示的是题目中没的航坐标和列坐标的数位之和不能大于k
        //这里我们传入第一个参数是i,第二个参数是j，第三个参数是count_i，第四个参数是count_j
        tmp.push({0,0,0,0});
        while(tmp.empty()!=true)
        {
            //用一个临时容器将我们队列中第一个点的信息提取出来
            vector<int> front=tmp.front();
            tmp.pop();
            //这里我们读取的第一个参数是i,第二个参数是j，第三个参数是count_i，第四个参数是count_j
            int i=front[0];
            int j=front[1];
            int count_i=front[2];
            int count_j=front[3];
            //如果当前结点已经越界了，或者当前结点的行列和相加已经超出我们的k了
            //或者我们当前的结点被记录过已经访问过了
            //就表名当前结点已经不满足题目的要求了，不可以移动了，我们就直接跳过本次循环，直接continue
            //注意下面的m,n,判断条件等号要取到
            if(i>=m||j>=n||count_i+count_j>k||recorded[i][j]==true)
            {
                continue;
            }
            //标记当前的结点已经访问过了
            recorded[i][j]=true;
            //我们当前的结点是满足条件的，所以就让我们的计数变量++
            result++;
            //向下遍历
            //向下遍历就是将我们的i坐标+1，但是相加之后我们需要判断新的i值的数位相加的结果的变化
            int new_count_i=0;
            if((i+1)%10==0)
            {
                //打个比方19的两位数相加原本是10，加一之后就变成了20，两位数相加的结果是2，也就是减小了8
                new_count_i=count_i-8;
            }
            else
            {
                //如果没有发生进位的话就直接+1
                new_count_i=count_i+1;
            }
            int new_count_j=0;
 
            //向右遍历
            //向右遍历就是将我们的j++
            //但是j++之后我们需要和之前一样判断我们的数位和的变化
            if((j+1)%10==0)
            {
                new_count_j=count_j-8;
            }
            else
            {
                //如果没有发生进位的话就直接+1
                new_count_j=count_j+1;
            }
            //将我们要遍历的新的结点入队
            tmp.push({i+1,j,new_count_i,count_j});
            tmp.push({i,j+1,count_i,new_count_j});
        }
        //返回我们的统计结果。
        return result;
    }
};