67 - 机器人的移动范围

题目：

地上有个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动，它每一次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子。

　　例如，当k为18时，机器人能够进入方格(35,37)，因为3+5+3+7=18.但它不能进入方格(35,38)，因为3+5+3+8=19.请问该机器人能够达到多少格子？

和上一题66 - 矩阵中的路径类似，只是约束条件发生了改变。

当机器人在某一个格子时，它能够向上下左右四个方向运动，当访问周围的格子时，标记为已访问，判断该格子坐标是否满足要求，满足则计数加 1，否则计数加 0. 当遍历完所有格子时，计数完毕。

bool CheckNum(int row, int col, int threshold); // 检查坐标是否满足要求
int MoveCountsCore(int rows, int cols, int row, int col, bool* visited, int threshold);

int MoveCounts(int threshold, int rows, int cols) {
    if (rows <  || cols <  || threshold < ) {
        return ;
    }
    bool* visited = new bool [rows*cols]; //访问记录
    for (int i = ; i < rows*cols; i++)
        visited[i] = false;
    int counts = MoveCountsCore(rows, cols, , , visited, threshold);
    delete []visited;
    return counts;
}

int MoveCountsCore(int rows, int cols, int row, int col, bool* visited, int threshold) {
    if (rows <  || cols <  || row <  || col <  || threshold < )
        return ;
    if (row < rows && col < cols && !visited[row*cols + col] && CheckNum(row, col, threshold)) {
        visited[row*cols + col] = true;
        return  + MoveCountsCore(rows, cols, row-, col, visited, threshold) +
                         MoveCountsCore(rows, cols, row, col-, visited, threshold) +
                         MoveCountsCore(rows, cols, row+, col, visited, threshold) +
                         MoveCountsCore(rows, cols, row, col+, visited, threshold);
    }
    return ;
}

// 检查坐标是否，满足要求
bool CheckNum(int row, int col, int threshold) {
    if (row <  || col <  || threshold< )
        return false;
    int bit_sum = ;
    while (row != ) {
        bit_sum += row % ;
        row /= ;
    }
    while (col != ) {
        bit_sum += col % ;
        col /= ;
    }
    if (bit_sum <= threshold)
        return true;
    else
        return false;
}
           

测试样例：

From 《剑指offer》 GitHub

// ================================ test code ================================
void test(char* testName, int threshold, int rows, int cols, int expected)
{
    if(testName != NULL)
        printf("%s begins: ", testName);

    if(MoveCounts(threshold, rows, cols) == expected)
        printf("Passed.\n");
    else
        printf("FAILED.\n");
}

void test1()
{
    test("Test1", , , , );
}

void test2()
{
    test("Test2", , , , );
}

void test3() 
{
    test("Test3", , , , );
}

void test4() 
{
    test("Test4", , , , );
}

void test5()
{
    test("Test5", , , , );
}

void test6()
{
    test("Test6", , , , );
}

void test7()
{
    test("Test7", , , , );
}

void test8()
{
    test("Test8", -, , , );
}

int main(int agrc, char* argv[])
{
    test1();
    test2();
    test3();
    test4();
    test5();
    test6();
    test7();
    test8();
}