//有一个m*N的方格，从（0，0）开始移动，每一次可以向上下左右移动一格，不能进入行列坐标的数位之和大于K的格子,机器人可以达到的最大格子数目?

#include <iostream>
#include<stdio.h>
using namespace std;
//判断能否进入坐标（row,col），主要在于获得各个数位
int getDigitNum(int number){
    int sum=0;
    while(number>0){
        sum+=number%10;
        number/=10;
    }
    return sum;
}
bool check(int threshold,int rows, int cols,int row, int col,bool * visited){
    if(row>=0 && row<rows && col>=0 && col<cols && getDigitNum(row)+getDigitNum(col)<=threshold &&!visited[row*cols+col])
        return true;
    return false;
}
int movingCountCore(int threshold,int rows,int cols,int row,int col,bool* visited);
int movingCount(int threshold,int rows,int cols){
    bool* visited=new bool[rows*cols];
    for(int i=0;i<rows*cols;i++)
        visited[i]=false;

    int countt=movingCountCore(threshold,rows,cols,0,0,visited);
    delete[] visited;
    return countt;
}

int movingCountCore(int threshold,int rows,int cols,int row,int col,bool* visited){
    int countt=0;
    if(check(threshold,rows,cols,row,col,visited)){
        visited[row*cols+col]=true;

        countt=1+movingCountCore(threshold,rows,cols,row-1,col,visited)+
                movingCountCore(threshold,rows,cols,row,col-1,visited)+
                movingCountCore(threshold,rows,cols,row+1,col,visited)+
                movingCountCore(threshold,rows,cols,row,col+1,visited);

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

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

void test1()
{
    test("Test1", 5, 10, 10, 21);
}

void test2()
{
    test("Test2", 15, 20, 20, 359);
}

void test3()
{
    test("Test3", 10, 1, 100, 29);
}

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

void test5()
{
    test("Test5", 15, 100, 1, 79);
}

void test6()
{
    test("Test6", 15, 10, 1, 10);
}

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

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

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