백준2172 팰린드롬 경로

작성일 | In

문제 링크

  • http://icpc.me/2172

사용 알고리즘

  • DP

시간복잡도

  • $O(N^4L)$

풀이

$D(i_1, j_1, i_2, j_2, l) = $ $(i_1, j_1)$에서 시작하고 $(i_2, j_2)$에서 끝나는 길이가 $l$인 팰린드롬의 개수
로 DP를 정의하면 각 상태 당 $8^2 = 64$가지의 상태 전이만 고려해주면 됩니다.

$O(N^4L)$에 문제를 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
const int di[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dj[] = {0, 0, 1, -1, 1, -1, 1, -1};

int n, m, a[22][22];
ll dp[22][22][22][22][22];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin >> a[i][j];

    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        dp[i][j][i][j][1]++;
        for(int k=0; k<8; k++){
            int ii = i + di[k], jj = j + dj[k];
            if(ii < 1 || jj < 1 || ii > n || jj > n) continue;
            if(a[i][j] != a[ii][jj]) continue;
            dp[i][j][ii][jj][2]++;
        }
    }

    for(int len=3; len<=m; len++){
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
            for(int k=1; k<=n; k++) for(int s=1; s<=n; s++){
                if(a[i][j] != a[k][s]) continue;
                for(int d=0; d<8; d++) for(int dd=0; dd<8; dd++){
                    int ii = i + di[d], jj = j + dj[d];
                    int kk = k + di[dd], ss = s + dj[dd];
                    if(ii < 1 || jj < 1 || ii > n || jj > n) continue;
                    if(kk < 1 || ss < 1 || kk > n || ss > n) continue;
                    if(a[ii][jj] != a[kk][ss]) continue;
                    dp[ii][jj][kk][ss][len] += dp[i][j][k][s][len-2];
                }
            }
        }
    }

    ll ans = 0;
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) for(int k=1; k<=n; k++) for(int s=1; s<=n; s++) {
        ans += dp[i][j][k][s][m];
    }
    cout << ans;
}