20210707

机器人的运动范围
题目链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

思路：典型的回溯问题，需要考虑的点是满足数位和的格子呈什么样的分布特征？脑补一下函数图像，可以想到大概是一些三角形的形状，此处给出lc题解中的图：

画出这幅图之后可以得到一个结论，即机器人可以只通过向下和向右运动到达所有可以到达的格子，因此回溯时也只需考虑这两个方向。

参考代码：

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        return search(m, n, k, 0, 0, visited);
    }
    int search(int m, int n, int k, int x, int y, vector<vector<bool>>& visited) {
        if (bitSum(x) + bitSum(y) > k || x >= m || y >= n || visited[x][y]) {
            return 0;
        }
        visited[x][y] = true;
        return 1 + search(m, n, k, x + 1, y, visited) + search(m, n, k, x, y + 1, visited);
    }
    int bitSum(int num) {
        int sum = 0;
        while (num != 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
};