zoj1004

#include <iostream> #include <string> #include <stack> #include <fstream> using namespace std; char *pSrc = NULL; char *pDest = NULL; stack<char> s1; char res[1000]; int cnt = 0; void work(){ if(*pDest == '/0'){ for(int i = 0; i < cnt; i++){ cout << res[i] << " "; } cout << endl; return ; } if(*pSrc != '/0'){ s1.push(*pSrc); pSrc++; res[cnt] = 'i'; cnt++; work(); pSrc--; cnt--; s1.pop(); } if(!s1.empty()){ if(s1.top() == *pDest){ char c = s1.top(); s1.pop(); res[cnt] = 'o'; cnt++; pDest++; work(); s1.push(c); cnt--; pDest--; } } } int main(){ string strSrc; string strDest; while(cin >> strSrc >> strDest){ cnt = 0; pSrc = const_cast<char *> (strSrc.c_str()); pDest = const_cast<char *> (strDest.c_str()); cout << "[" << endl; work(); cout << "]" << endl; } return 0; }

 

回溯法，好久没做题了，工作之余抽空做做，练习练习c++和一些基本算法