미로에 갇힌 상근

Problem link: https://www.acmicpc.net/problem/5069

문제 자체는 크게 어렵지 않지만 좌표계가 6각형인 관계로 꽤나 애를 먹었다.

우상향하는 방향을 하나의 행으로 잡고, 총 29x29 크기의 배열로 생각하고 풀어주면 된다.

DP를 위한 캐시정의는 아래와 같다.

• CACHE[turn][row][col]: turn번의 이동에 걸쳐 row, col번째 육각형에 도착하는 경우의 수

점화식은 아래와 같이 세워줄 수 있다.

• CACHE[turn][row][col] += CACHE[trun-1][n_row][n_col] (n_row, n_col은 row, col번째 육각형에 인접한 육각형을 의미)

인접한 육각형을 찾는 부분이 조금 까다로웠는데, 결과적으로는 홀수번째 향에 있나 짝수번째 행에 있냐를 기준으로 dr, dc를 잘 설정해서 풀어주었다.

#include <iostream>

using namespace std;

const int kMaxN = 14;
const int kRows = kMaxN * 2 + 1;
const int kCols = kMaxN * 2 + 1;

int CACHE[kMaxN + 1][kRows][kCols];

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Preprocess
  const int dr[2][6] = { { -1, 0, 1, 1, 0, -1 }, { -1, 0, 1, 1, 0, -1 } };
  const int dc[2][6] = { { 0, 1, 0, -1, -1, -1 }, { 1, 1, 1, 0, -1, 0 } };

  CACHE[0][kMaxN][kMaxN] = 1;

  for (int turn = 1; turn <= kMaxN; ++turn)
  {
    for (int row = 0; row < kRows; ++row)
    {
      for (int col = 0; col < kCols; ++col)
      {
        for (int dir = 0; dir < 6; ++dir)
        {
          int nrow = row + dr[row % 2][dir];
          int ncol = col + dc[row % 2][dir];
          if (0 > nrow || nrow >= kRows || 0 > ncol || ncol >= kCols)
          {
            continue;
          }

          CACHE[turn][row][col] += CACHE[turn - 1][nrow][ncol];
        }
      }
    }
  }

  int tc;
  cin >> tc;

  while (tc--)
  {
    int turn;
    cin >> turn;
    cout << CACHE[turn][kMaxN][kMaxN] << '\n';
  }

  return 0;
}