BOJ 5069 - 미로에 갇힌 상근

BOJ 5069 - 미로에 갇힌 상근

이런 벌집류 문제는 $6$방향으로 BFS를 돌릴 수 있고 이 문제는 단순한 DP문제이다.

map<int, map<int, map<int, int>>> dp;

int dy[] = {-1, 0, 1, 1, 0, -1};
int dx[] = {0, 1, 1, 0, -1, -1};

int fn(int y, int x, int remain) {
   if (remain == 0) {
      return y == 0 && x == 0;
   }
   if (hass(dp[y][x], remain)) {
      return dp[y][x][remain];
   }
   int &ret = dp[y][x][remain];
   for (int d = 0; d < 6; d++) {
      int ny = y + dy[d];
      int nx = x + dx[d];
      ret += fn(ny, nx, remain - 1);
   }
   return ret;
}

void solve() {
   int n;
   cin >> n;
   cout << fn(0, 0, n) << endl;
}