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

int movingCount(int threshold, int rows, int cols) {
    // 计数器
    int count = 0;

    // 记录某坐标能否到达的标记
    vector<vector<int>> flags;

    for(int  i = 0; i < rows; i++) {

        // 计算行号的 threshold
        int ts_r =  i/10 + i%10;

        //定义当前行的flags
        vector<int> line;

        for(int j = 0; j < cols; j++) {

            //当前坐标的 threshold
            int ts = ts_r + j/10 + j%10;

            // 1, ts <= threshold 是可达的必要条件
            // 2, [0, 0] 为 可达的 初始条件
            // 3, [i-1, j] 可达 或 [i, j-1] 可达， 为[i, j] 可达的必要条件
            if (ts <= threshold && ((i==0&&j==0) || (i >0 && flags[i-1][j] == 1) || (j > 0 && line[j - 1] == 1))) {
                count++;
                line.push_back(1);
            } else {
                line.push_back(0);
            }
        }
        flags.push_back(line);
    }
    return count;
}