剑指offer 13 机器人在矩阵中移动

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

这也是一道"连续移动"的问题, 很容易联想到广度优先搜索, 进而联想到使用递归.
这道题一个陷阱就是:不要试图先寻找边界, 因为机器人连续移动. 举个例子:有可能[20][20]满足要求, 但是无法从任何邻接的地方进入. 老老实实递归才是硬道理.

int count(int a, int b, int m, int n, int k, int **mark)
{
    int result = 0;
    if((a>=m) || (b>=n) ||(a<0) || (b<0)) return 0;
    if(mark[a][b] == 1)return 0;
    if((a%10) + (a/10) + (b%10) + (b/10) <= k)
    {
        result++;
        mark[a][b] = 1;
        result +=count(a+1, b, m, n, k, mark);
        result +=count(a-1, b, m, n, k, mark);
        result +=count(a, b+1, m, n, k, mark);
        result +=count(a, b-1, m, n, k, mark);
    }

    return result;
}




int movingCount(int m, int n, int k){
  int result = 0;
  int **mark = (int**)malloc(sizeof(int*) * m);
  for(int i = 0; i< m; i++)
    mark[i] = (int*)malloc(sizeof(int) * n);

    for(int i = 0; i < m; i++)
        for(int j = 0; j< n; j++)
            mark[i][j] = 0;

    result += count(0, 0, m, n, k, mark);

    return result;
}