ccbeginner

UVa Q164 (!finish)

Feb 11th, 2020
122
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q164
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int dp[22][22];
  6. int track[22][22];//0 := copy, 1 := →, 2 := ↓, 3 := ↘
  7.  
  8. string s1, s2;
  9.  
  10. void back(int x, int y){
  11.     //cout << x << ' ' << y << ' ' << endl;
  12.     if(x == 0 && y == 0)return;
  13.     if(track[x][y] == 0)back(x-1, y-1);
  14.     else if(track[x][y] == 1){
  15.         back(x, y-1);
  16.         printf("I%c%02d", s2[y], y);
  17.     }else if(track[x][y] == 2){
  18.         back(x-1, y);
  19.         printf("D%c%02d", s1[x], y+1);
  20.     }else if(track[x][y] == 3){
  21.         back(x-1, y-1);
  22.         printf("C%c%02d", s2[y], y);
  23.     }
  24. }
  25.  
  26. int32_t main(){
  27.     for(int i = 1; i <= 20; ++i){
  28.         track[0][i] = 1;
  29.         track[i][0] = 2;
  30.         dp[0][i] = dp[i][0] = i;
  31.     }
  32.     while(cin >> s1 >> s2){
  33.         s1 = ' ' + s1;
  34.         s2 = ' ' + s2;
  35.         for(unsigned i = 1; i < s1.size(); ++i){
  36.             for(unsigned j = 1; j < s2.size(); ++j){
  37.                 dp[i][j] = 1e9;
  38.                 if(s1[i] == s2[j]){
  39.                     track[i][j] = 0;
  40.                     dp[i][j] = dp[i-1][j-1];
  41.                 }else{
  42.                     track[i][j] = 3;
  43.                     dp[i][j] = dp[i-1][j-1] + 1;
  44.                 }
  45.                 if(dp[i][j-1] + 1 < dp[i][j]){
  46.                     dp[i][j] = dp[i][j-1] + 1;
  47.                     track[i][j] = 1;
  48.                 }
  49.                 if(dp[i-1][j] + 1 < dp[i][j]){
  50.                     dp[i][j] = dp[i-1][j] + 1;
  51.                     track[i][j] = 2;
  52.                 }
  53.             }
  54.         }
  55.         /*for(int i = 1; i < s1.size(); ++i){
  56.             for(int j = 1; j < s2.size(); ++j)cout << dp[i][j] << ' ';
  57.             cout << '\n';
  58.         }*/
  59.         back(s1.size()-1, s2.size()-1);
  60.         cout << "E\n";
  61.     }
  62.     return 0;
  63. }
RAW Paste Data