C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-07-04

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

const int N = 100;

// ------------ function prototype -----------
// debug helper function
void printGrid(int (*p)[N], const int m, const int n);
// algorithm fucntion
int DFS(int (*p)[N], const int m, const int n, int k, int x, int y);
bool available(int (*p)[N], const int x, const int y, const int m, const int n, int k);

int main(const int argc, const char** argv) {
  int m, n, k;
  scanf("%d %d %d", &m, &n, &k);
  
  int grid[N][N];
  memset(grid, 0x0000, sizeof grid);
   
  return printf("%d", DFS(grid, m, n, k, 0, 0)), 0;
}

void printGrid(int (*p)[N], const int m, const int n) {
  int x, y;
  for (y = 0; y < m; ++y) {
    for (x = 0; x < n; ++x)
      printf("%d ", *(*(p + y) + x));
    putchar('\n');
  }
}

static const int dirs[] = { 0, -1, 0, 1, 0 };

bool available(int (*p)[N], const int x, const int y, const int m, const int n, int k) {
  if (x < 0 || y < 0 || x == n || y == m || *(*(p + y) + x))
    return false;
  
  int s = 0, row = y, col = x;
  while (row) {
    s += row % 10;
    row /= 10;
  }
  while (col) {
    s += col % 10;
    col /= 10;
  }
  return s <= k;
}

int DFS(int (*p)[N], const int m, const int n, int k, int x, int y) {
  if (!available(p, x, y, m, n, k)) return 0;
  
  *(*(p + y) + x) = 1; // mark as visited
  
  int i, ret = 1;
  for (i = 0; i < 4; ++i)
    ret += DFS(p, m, n, k, x + dirs[i], y + dirs[i + 1]);
    
  return ret;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 408KB, 提交时间: 2020-09-05

#include <bits/stdc++.h>
using namespace std;

int dfs(int x, int y, int m, int n, int sum, vector<vector<int>>& arr) {
 
    if ( x < 0 || x > m-1 || y<0 || y >n-1 || arr[x][y] == 1 || (x / 10 + x % 10 + y / 10 + y % 10)>sum) {
        return 0;
    }
    arr[x][y] = 1;
    return dfs(x + 1, y, m, n, sum, arr) + dfs(x, y + 1, m, n, sum, arr) + 1;
 
 
}
int main() {
    int m = 0;
    int n = 0;
    int target = 0;
    cin >> m;
    cin >> n;
    cin >> target;
    vector<vector<int> > arr(m, vector<int>(n, 0));
    int res = dfs(0, 0, m, n, target,arr);
    cout << res << endl;
    return 0;
}