SMMR-110: Magic Spell IV

#include <bits/stdc++.h>

using namespace std;
const int N = 60 + 10;
const int INF = 60 * 4;
char A[N], B[N], C[N], D[N];
int dp[N][N][N][N];
int la, lb, lc, ld;

bool check(int a, int b, int c, int d){
    return a <= la and b <= lb and c <= lc and d <= ld;
}

int f(int a, int b, int c, int d){
    if(a == la and b == lb and c == lc and d == ld) return 0;

    if(dp[a][b][c][d] != INF) return dp[a][b][c][d];

    int cnt = INF;
    /// 4
    if(check(a + 1, b + 1, c + 1, d + 1) and A[a] == B[b] and B[b] == C[c] and C[c] == D[d])
        cnt = min(cnt, 1 + f(a + 1, b + 1, c + 1, d + 1));

    /// 3
    if(check(a + 1, b + 1, c + 1, d) and A[a] == B[b] and B[b] == C[c])
        cnt = min(cnt, 1 + f(a + 1, b + 1, c + 1, d));

    if(check(a + 1, b + 1, c, d + 1) and A[a] == B[b] and B[b] == D[d])
        cnt = min(cnt, 1 + f(a + 1, b + 1, c, d + 1));

    if(check(a + 1, b, c + 1, d + 1) and A[a] == C[c] and C[c] == D[d])
        cnt = min(cnt, 1 + f(a + 1, b, c + 1, d + 1));

    if(check(a, b + 1, c + 1, d + 1) and B[b] == C[c] and C[c] == D[d])
        cnt = min(cnt, 1 + f(a, b + 1, c + 1, d + 1));

    /// 2
    if(check(a + 1, b + 1, c, d) and A[a] == B[b])
        cnt = min(cnt, 1 + f(a + 1, b + 1, c, d));

    if(check(a + 1, b, c + 1, d) and A[a] == C[c])
        cnt = min(cnt, 1 + f(a + 1, b, c + 1, d));

    if(check(a + 1, b, c, d + 1) and A[a] == D[d])
        cnt = min(cnt, 1 + f(a + 1, b, c, d + 1));

    if(check(a, b + 1, c, d + 1) and B[b] == D[d])
        cnt = min(cnt, 1 + f(a, b + 1, c, d + 1));

    if(check(a, b + 1, c + 1, d) and B[b] == C[c])
        cnt = min(cnt, 1 + f(a, b + 1, c + 1, d));

    if(check(a, b, c + 1, d + 1) and C[c] == D[d])
        cnt = min(cnt, 1 + f(a, b, c + 1, d + 1));

    /// 1
    if(check(a + 1, b, c, d))
        cnt = min(cnt, 1 + f(a + 1, b, c, d));

    if(check(a, b + 1, c, d))
        cnt = min(cnt, 1 + f(a, b + 1, c, d));

    if(check(a, b, c + 1, d))
        cnt = min(cnt, 1 + f(a, b, c + 1, d));

    if(check(a, b, c, d + 1))
        cnt = min(cnt, 1 + f(a, b, c, d + 1));

    return dp[a][b][c][d] = cnt;
}

int main(){

    scanf("%s", A);
    scanf("%s", B);
    scanf("%s", C);
    scanf("%s", D);

    la = strlen(A), lb = strlen(B), lc = strlen(C), ld = strlen(D);

    for(int a = 0; a < la; a ++)
        A[a] = tolower(A[a]);
    for(int b = 0; b < lb; b ++)
        B[b] = tolower(B[b]);
    for(int c = 0; c < lc; c ++)
        C[c] = tolower(C[c]);
    for(int d = 0; d < ld; d ++)
        D[d] = tolower(D[d]);

    for(int a = la; a >= 0; a --){
        for(int b = lb; b >= 0; b --){
            for(int c = lc; c >= 0; c --){
                for(int d = ld; d >=0; d--){
                    if(a == la and b == lb and c == lc and d == ld) {
                        dp[a][b][c][d] = 0;
                        continue;
                    }

                    int cnt = INF;
                    /// 4
                    if(check(a + 1, b + 1, c + 1, d + 1) and A[a] == B[b] and B[b] == C[c] and C[c] == D[d])
                        cnt = min(cnt, 1 + dp[a + 1][b + 1][c + 1][d + 1]);

                    /// 3
                    if(check(a + 1, b + 1, c + 1, d) and A[a] == B[b] and B[b] == C[c])
                        cnt = min(cnt, 1 + dp[a + 1][b + 1][c + 1][d]);

                    if(check(a + 1, b + 1, c, d + 1) and A[a] == B[b] and B[b] == D[d])
                        cnt = min(cnt, 1 + dp[a + 1][b + 1][c][d + 1]);

                    if(check(a + 1, b, c + 1, d + 1) and A[a] == C[c] and C[c] == D[d])
                        cnt = min(cnt, 1 + dp[a + 1][b][c + 1][d + 1]);

                    if(check(a, b + 1, c + 1, d + 1) and B[b] == C[c] and C[c] == D[d])
                        cnt = min(cnt, 1 + dp[a][b + 1][c + 1][d + 1]);

                    /// 2
                    if(check(a + 1, b + 1, c, d) and A[a] == B[b])
                        cnt = min(cnt, 1 + dp[a + 1][b + 1][c][d]);

                    if(check(a + 1, b, c + 1, d) and A[a] == C[c])
                        cnt = min(cnt, 1 + dp[a + 1][b][c + 1][d]);

                    if(check(a + 1, b, c, d + 1) and A[a] == D[d])
                        cnt = min(cnt, 1 + dp[a + 1][b][c][d + 1]);

                    if(check(a, b + 1, c, d + 1) and B[b] == D[d])
                        cnt = min(cnt, 1 + dp[a][b + 1][c][d + 1]);

                    if(check(a, b + 1, c + 1, d) and B[b] == C[c])
                        cnt = min(cnt, 1 + dp[a][b + 1][c + 1][d]);

                    if(check(a, b, c + 1, d + 1) and C[c] == D[d])
                        cnt = min(cnt, 1 + dp[a][b][c + 1][d + 1]);

                    /// 1
                    if(check(a + 1, b, c, d))
                        cnt = min(cnt, 1 + dp[a + 1][b][c][d]);

                    if(check(a, b + 1, c, d))
                        cnt = min(cnt, 1 + dp[a][b + 1][c][d]);

                    if(check(a, b, c + 1, d))
                        cnt = min(cnt, 1 + dp[a][b][c + 1][d]);

                    if(check(a, b, c, d + 1))
                        cnt = min(cnt, 1 + dp[a][b][c][d + 1]);

                    dp[a][b][c][d] = cnt;
                }
            }
        }
    }

    printf("%d", dp[0][0][0][0]);

    return 0;
}