UVa732

UVa732
バックトラックするだけ。

view plainprint?

1. #include <iostream>  
2. #include <algorithm>  
3. #include <vector>  
4. #include <set>  
5. #include <map>  
6. #include <queue>  
7. #include <stack>  
8.   
9. #include <cstdio>  
10. #include <cstring>  
11. #include <cstdlib>  
12. #include <cmath>  
13.   
14. #define REP(i, n) for(int i=0; i<(int)n; ++i)  
15. #define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)  
16. #define ALL(c) (c).begin(),(c).end()  
17.   
18. typedef long long int lli;  
19.   
20. using namespace std;  
21.   
22. stack<char> S;  
23.   
24. char buff[1000];  
25.   
26. void bt(string s, string t, int idx)  
27. {  
28.   if (s.empty() && t.empty()) {  
29.     for (int i = 0; i < idx; ++i) {  
30.       if (i) cout << ' ';  
31.       cout << buff[i];  
32.     }  
33.     cout << endl;  
34.     return ;  
35.   }  
36.   if (s.size()) {  
37.     buff[idx] = 'i';  
38.     S.push(s[0]);  
39.     bt(s.substr(1), t, idx + 1);  
40.     S.pop();  
41.   }   
42.   if (t.size() && S.size() && S.top() == t[0]) {  
43.     buff[idx] = 'o';  
44.     S.pop();  
45.     bt(s, t.substr(1), idx + 1);  
46.     S.push(t[0]);  
47.   }  
48.   return ;  
49. }  
50.   
51. int main(int argc, char *argv[])  
52. {  
53.   string s, t;  
54.   while (cin >> s >> t) {  
55.     S = stack<char>();  
56.     cout << "[" << endl;  
57.     if (s.size() == t.size()) bt(s, t, 0);  
58.     cout << "]" << endl;  
59.   }  
60.   return 0;  
61. }  

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()

typedef long long int lli;

using namespace std;

stack<char> S;

char buff[1000];

void bt(string s, string t, int idx)
{
  if (s.empty() && t.empty()) {
    for (int i = 0; i < idx; ++i) {
      if (i) cout << ' ';
      cout << buff[i];
    }
    cout << endl;
    return ;
  }
  if (s.size()) {
    buff[idx] = 'i';
    S.push(s[0]);
    bt(s.substr(1), t, idx + 1);
    S.pop();
  } 
  if (t.size() && S.size() && S.top() == t[0]) {
    buff[idx] = 'o';
    S.pop();
    bt(s, t.substr(1), idx + 1);
    S.push(t[0]);
  }
  return ;
}

int main(int argc, char *argv[])
{
  string s, t;
  while (cin >> s >> t) {
    S = stack<char>();
    cout << "[" << endl;
    if (s.size() == t.size()) bt(s, t, 0);
    cout << "]" << endl;
  }
  return 0;
}