#include <stdio.h>
#include <float.h>
#include <errno.h>
#include <assert.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>

/*
 题目: 
    地上右一个 m 行 n 列的方格. 
    一个机器人从坐标(0, 0) 的格子开始移动, 它每次可以向左, 右, 上, 下移动一格, 
    但不能进入行坐标和列坐标的数位之和大于 k 的格子. 例如, 当 k 为 18 的时候,
    机器人能够进入方格 (35, 37), 因为 3 + 5 + 3 + 7 = 18. 
    但它不能进入方格 (35, 38), 因为 3 + 5 + 3 + 9 = 19.
    请问该机器人能够到达多少个格子?
 */

extern int moving_count(int m, int n, int threshold);

int main(int argc, char * argv[]) {
    int m = 20, n = 20, threshold = 10;
    int count = moving_count(m, n, threshold);
    printf("<m = %d, n = %d, threshold = %d> -> %d\n", m, n, threshold, count);
    return 0;
}

struct visite {
    int  rows;
    int  cols;
    int  threshold;
    bool visited[];
};

inline struct visite * visite_create(int rows, int cols, int threshold) {
    struct visite * v = malloc(sizeof(struct visite) + (rows * cols) * sizeof (int));
    assert(v && rows > 0 && cols > 0 && threshold > 0);
    v->rows = rows;
    v->cols = cols;
    v->threshold = threshold;
    memset(v->visited, 0, (rows * cols) * sizeof (int));
    return v;
}

inline void visite_delete(struct visite * v) {
    if (v) free(v);
}

static inline int get_digit_sum(int num) {
    int sum = 0;
    while (num > 0) {
        sum = num % 10;
        num /= 10;
    }
    return sum;
}

inline bool visite_check(struct visite * v, int row, int col) {
    if (row >= 0 && row < v->rows && col >= 0 && col < v->cols && !v->visited[row * v->cols + col]) {
        return get_digit_sum(row) + get_digit_sum(col) <= v->threshold;
    }
    return false;
}

int visite_moving(struct visite * v, int row, int col) {
    if (!visite_check(v, row, col))
        return 0;

    v->visited[row * v->cols + col] = true;
    return 1 + visite_moving(v, row, col - 1) 
             + visite_moving(v, row, col + 1) 
             + visite_moving(v, row - 1, col) 
             + visite_moving(v, row + 1, col);
}

int 
moving_count(int m, int n, int threshold) {
    if (m < 0 || n < 0 || threshold < 0)
        return 0;
    if (threshold == 0)
        return 1;

    struct visite * v = visite_create(m, n, threshold);

    int count = visite_moving(v, 0, 0);

    visite_delete(v);

    return count;
}