66.机器人的运动范围.md

66.机器人的运动范围

题目描述

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

 

解题思路

不是很难，类似深度优先搜索dfs即可解决，只是有些细节有点难理清楚，详见注释，由于进入过的格子会被标记，因此不会重复进入，迭代的复杂度不会很高，仔细想想的话递归其实也可以。没有必要向左和向上搜索，因为按题目中的条件，如果某个格子不行的话，那么该格子所在的对角线往左下角方向的所有格子都不行，但是往右上角的格子是可能可以进的，因为可能出现当前格子为39，右上角为40 。迭代的话可以创建相同大小的网格，每一行扫描过去，每个格子能否进入取决于其左边和上边格子的或运算，初始化时初始位置可以进，其他位置全置0，遇到不能进的格子则右边停止扫描。

如果是问总共有多少条路径的话（一般限制只能向右和向上，不然四个方向都能走的话就太复杂了），就用动态规划来解，创建一个与网格相同大小的数组，里面存储走到每个格子有多少条路径，遇到不能走的位置就把该位置的路径数置0，不能用递归，因为递归的话很多格子会重复进入，递归层数太多，复杂度太高，无法通过。用迭代的话就每一行扫描过去，每个格子的路径数就是其左边和下面格子中的数字之和（因为每个格子只能由左边或者下面进来，可以先把首行和首列进行初始化，均为1，遇到boss就停止，因为boss后面去不了，因此都是0）。

 

代码

• 思路一，排序后取中位数

class Solution {
private:
    int count;
    void search(char* flags, int row, int column, int threshold, int rows, int cols){
        int idx = row*cols+column;
        if(row<0 || column<0 || row>=rows || column>=cols || flags[idx]) return;
        // 以上条件不满足的话说明这个格子没走过，设置标志位
        flags[idx] = 1;
        int sum = splitSum(row) + splitSum(column);
        // 数位和大于threshold的格子根本不能进，更别说从该格子继续往外搜索了
        // 因此直接返回
        if(sum > threshold) return;
        count++;
        // 从左上角开始进行dfs，深度优先搜索
        // 没必要向左和向上搜索，因为如果某个格子不能进的话，
        // 那么该格子所在的对角线往左下角方向的所有格子都不行
        // 但是往右上角的格子是可能可以进的，因为可能出现当前格子为39，右上角为40
        search(flags, row+1, column, threshold, rows, cols);
        search(flags, row, column+1, threshold, rows, cols);
    }
    
    int splitSum(int num){
        int sum = 0;
        while(num > 0){
            sum += num%10;
            num /= 10;
        }
        return sum;
    }
public:
    int movingCount(int threshold, int rows, int cols)
    {
        char flags[rows*cols];
        memset(flags, 0, sizeof(flags));
        count = 0;
        search(flags, 0, 0, threshold, rows, cols);
        return count;
    }
};