mickypinata

SMMR-T110: Magic Spell IV

Jul 27th, 2021 (edited)
478
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 60;
  5.  
  6. int dp[N + 1][N + 1][N + 1][N + 1], len[5];
  7. char *str[5];
  8.  
  9. bool notZero(int a, int b, int c, int d){
  10.     return a != 0 && b != 0 && c != 0 && d != 0;
  11. }
  12. bool notZero(int a, int b, int c){
  13.     return a != 0 && b != 0 && c != 0;
  14. }
  15. bool notZero(int a, int b){
  16.     return a != 0 && b != 0;
  17. }
  18.  
  19. int main(){
  20.  
  21.     for(int i = 1; i <= 4; ++i){
  22.         str[i] = new char[N + 1];
  23.         scanf(" %s", str[i] + 1);
  24.         len[i] = strlen(str[i] + 1);
  25.         for(int j = 1; j <= len[i]; ++j){
  26.             str[i][j] = tolower(str[i][j]);
  27.         }
  28.     }
  29.  
  30.     for(int a = 0; a <= len[1]; ++a){
  31.         for(int b = 0; b <= len[2]; ++b){
  32.             for(int c = 0; c <= len[3]; ++c){
  33.                 for(int d = 0; d <= len[4]; ++d){
  34.                     if(a == 0 && b == 0 && c == 0 && d == 0){
  35.                         dp[a][b][c][d] = 0;
  36.                         continue;
  37.                     }
  38.                     int mn = 1e9;
  39.                     // Four Parts
  40.                     if(notZero(a, b, c, d) && str[1][a] == str[2][b] && str[2][b] == str[3][c] && str[3][c] == str[4][d]){
  41.                         mn = min(mn, 1 + dp[a - 1][b - 1][c - 1][d - 1]);
  42.                     }
  43.                     // Three Parts
  44.                     if(notZero(a, b, c) && str[1][a] == str[2][b] && str[2][b] == str[3][c]){
  45.                         mn = min(mn, 1 + dp[a - 1][b - 1][c - 1][d]);
  46.                     }
  47.                     if(notZero(a, b, d) && str[1][a] == str[2][b] && str[2][b] == str[4][d]){
  48.                         mn = min(mn, 1 + dp[a - 1][b - 1][c][d - 1]);
  49.                     }
  50.                     if(notZero(a, c, d) && str[1][a] == str[3][c] && str[3][c] == str[4][d]){
  51.                         mn = min(mn, 1 + dp[a - 1][b][c - 1][d - 1]);
  52.                     }
  53.                     if(notZero(b, c, d) && str[2][b] == str[3][c] && str[3][c] == str[4][d]){
  54.                         mn = min(mn, 1 + dp[a][b - 1][c - 1][d - 1]);
  55.                     }
  56.                     // Two Parts
  57.                     if(notZero(a, b) && str[1][a] == str[2][b]){
  58.                         mn = min(mn, 1 + dp[a - 1][b - 1][c][d]);
  59.                     }
  60.                     if(notZero(a, c) && str[1][a] == str[3][c]){
  61.                         mn = min(mn, 1 + dp[a - 1][b][c - 1][d]);
  62.                     }
  63.                     if(notZero(a, d) && str[1][a] == str[4][d]){
  64.                         mn = min(mn, 1 + dp[a - 1][b][c][d - 1]);
  65.                     }
  66.                     if(notZero(b, c) && str[2][b] == str[3][c]){
  67.                         mn = min(mn, 1 + dp[a][b - 1][c - 1][d]);
  68.                     }
  69.                     if(notZero(b, d) && str[2][b] == str[4][d]){
  70.                         mn = min(mn, 1 + dp[a][b - 1][c][d - 1]);
  71.                     }
  72.                     if(notZero(c, d) && str[3][c] == str[4][d]){
  73.                         mn = min(mn, 1 + dp[a][b][c - 1][d - 1]);
  74.                     }
  75.                     // One Part
  76.                     if(a != 0){
  77.                         mn = min(mn, 1 + dp[a - 1][b][c][d]);
  78.                     }
  79.                     if(b != 0){
  80.                         mn = min(mn, 1 + dp[a][b - 1][c][d]);
  81.                     }
  82.                     if(c != 0){
  83.                         mn = min(mn, 1 + dp[a][b][c - 1][d]);
  84.                     }
  85.                     if(d != 0){
  86.                         mn = min(mn, 1 + dp[a][b][c][d - 1]);
  87.                     }
  88.                     dp[a][b][c][d] = mn;
  89.                 }
  90.             }
  91.         }
  92.     }
  93.     cout << dp[len[1]][len[2]][len[3]][len[4]];
  94.  
  95.     return 0;
  96. }
  97.  
RAW Paste Data