UVA 10981 - String Morphing（记忆化搜索） - c++编程基础

题目链接：10981 - String Morphing

题意：给定开始的字符串，要求根据表格变化成一个字符串，问变化的顺序（注意，不一定要最少步数）思路：记忆化搜索，用map来存字符串的状态，一开始按最少步数去做TLE，其实只要找到一个符合的就可以了代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
       using namespace std; #define min(a,b) ((a)<(b) (a):(b)) #define INF 0x3f3f3f3f const int N = 105; int t; string start, end; char g[105][105]; map
       
         dp; map
        
          z; int dfs(string start) { if (dp.count(start)) return dp[start]; dp[start] = 0; if (start == end) return dp[start] = 1; for (int i = 0; i < start.size() - 1; i++) { string tmp = ""; tmp += g[start[i]][start[i + 1]]; string s = start; if (dfs(s.replace(i, 2, tmp))) { z[start] = s; return dp[start] = 1; } } return dp[start]; } void print(string start) { cout << start << endl; if (start == end) return; print(z[start]); } int main() { g['a']['a'] = g['a']['b'] = g['b']['b'] = 'b'; g['a']['c'] = g['b']['c'] = g['c']['a'] = 'a'; g['b']['a'] = g['c']['b'] = g['c']['c'] = 'c'; scanf("%d", &t); while (t--) { z.clear(); dp.clear(); cin >




> start >> end; if (start.size() < end.size()) { printf("None exist!\n"); continue; } if (dfs(start)) print(start); else printf("None exist!\n"); if (t) printf("\n"); } return 0; }