leetcode-go/bailian/4103.walk-on-grid/main.cc

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 20;

bool flag[N + 1][2 * N + 1];

int dfs(int x, int y, int n) {
  if (n == 0) return 1;
  int cnt = 0;
  flag[x][y] = true;
  if (!flag[x + 1][y]) cnt += dfs(x + 1, y, n - 1);
  if (!flag[x][y + 1]) cnt += dfs(x, y + 1, n - 1);
  if (!flag[x][y - 1]) cnt += dfs(x, y - 1, n - 1);
  flag[x][y] = false;
  return cnt;
}

int main() {
  int n;
  scanf("%d", &n);
  memset(flag, 0, sizeof(flag));
  printf("%d\n", dfs(0, N, n));
  return 0;
}