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

class Solution {
  public:
    int fun(int x){
        int sum = 0;
        while(x != 0){
            sum += (x % 10);
            x /= 10;
        }
        return sum;
    }

    int tmp[100][100];

    void dfs(int x, int y, int max_x, int max_y, int target) {
        if (x >= max_x || y >= max_y || x < 0 || y < 0) {
            return;
        }
        if(fun(x) + fun(y) > target)return;

        tmp[x][y] = 1;

        //上
        if (x != 0 && tmp[x - 1][y] == 0) {
            dfs(x - 1, y, max_x, max_y, target);
        }
        //下
        if (x != max_x - 1 && tmp[x + 1][y] == 0) {
            dfs(x + 1, y, max_x, max_y, target);
        }
        //左
        if (y != 0 && tmp[x][y - 1] == 0) {
            dfs(x, y - 1, max_x, max_y, target);
        }
        //右
        if (y != max_y - 1 && tmp[x][y + 1] == 0) {
            dfs(x, y + 1, max_x, max_y, target);
        }
    }
    int movingCount(int threshold, int rows, int cols) {
        memset(tmp, 0, 10000);
        dfs(0, 0, rows, cols, threshold);
        int res = 0;
        for(int i = 0;i < 100;i++){
            for(int j = 0;j < 100;j++){
                if(tmp[i][j] == 1)res+=1;
            }
        }
        return res;
    }
};

题解：该题使用有记忆的暴力回溯，如果是无记忆会超时。从头开始，如果遍历到的坐标超出范围，那么则返回；如果在范围内，就判断这个坐标是否符合小于等于target，如果不符合则返回。符合，那么就将这个坐标加入结果集中。然后准备进入上下左右相邻的坐标进行递归，如果它的位置符合移动的要求，并且该点未被遍历过（因为如果再次遍历，就重复了，因为上一次已经从该点探测过结果了），那么就进入该节点进行递归。上下左右遍历完就结束。时间复杂度是O(m*n)，空间复杂度是O(m*n)。