int digitSum(int i) {
    int sum = 0, num = i;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

int dfsTraversal(int x, int y, int m, int n, bool** visited, int k) {
    // 特判，返回0表示不能到达。
    // 1、超出边界
    //2、位数和不满足小于等于k的条件
    // 3、当前节点已经访问过
    //
    if (x < 0 || y < 0 || x >= m || y >= n 
        || digitSum(x) + digitSum(y) > k
        || visited[x][y] == true) {
        return 0;
    }
    // 标记当前节点已到达 
    visited[x][y] = true;
    // 再次进入下一层递归
     // 这里只遍历了右、下，左、上不需要遍历，
     // 因为是从左上开始的，到右下结束，所以当前节点都是从左上来的
    return 1 + dfsTraversal(x, y + 1, m, n, visited, k)
    + dfsTraversal(x + 1, y, m, n, visited, k);
}
int movingCount(int m, int n, int k) {
    // 路径数组，用于存放遍历结果 
    bool** visited = (bool**)malloc(sizeof(bool*) * m);
    for (int i = 0; i < m; i++) {
        visited[i] = (bool*)calloc(n, sizeof(bool));
    }
    // dfs深度搜索 
    return dfsTraversal(0, 0, m, n, visited, k);
}