ZOJ Problem Set - 1004（回溯法)

Problem Set - 1004（回溯法)"/>

ZOJ Problem Set - 1004（回溯法)

题目链接

Sample Input
madam
adamm
bahama
bahama
long
short
eric
rice

Sample Output
[
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
[
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
]
[
i i o i o i o o
]

思路：一开始想到二叉树去了，但是后来想来想去构建一棵树很困难，然后改变思路，我想着这其实就是枚举，把每一种路径枚举出来再与目标字符串比较一遍，再就想到前些天刚接触的回溯法，试着写了代码，然后找到思路就把这道题A了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
char M[10010], M2[10010], temp[10010], ss[10010];
char cmd[2] = { 'i', 'o' };
int len;
stack<char> t2;void test(int curw) {cout << "--------------------------" << endl;cout << curw << endl;for (int i = 0; i <= curw; i++) {printf("%c", ss[i]);}putchar('\n');
}void T(int cur, int curw) {if (cur <= len * 2) {//test(curw);for (int i = 0; i < 2; i++) {if (cmd[i] == 'i' && t2.size() < len) {t2.push('i');  //做限制条件的栈，栈满不可入栈ss[curw] = 'i';T(cur + 1, curw + 1);t2.pop();  // 记得还原栈的状态}if (cmd[i] == 'o' && t2.size() > 0) { //栈空不可出栈t2.pop();ss[curw] = 'o';T(cur + 1, curw + 1);t2.push('i');}}}else {int curv, curx;  //对于每一种路径都一一比较curv = curx = 0;stack<char> t;memset(temp, 0, sizeof(temp));for (int i = 0;i < curw; i++) {if (ss[i] == 'i' && t.size() < len) {t.push(M[curv++]);}else if(t.size() > 0){temp[curx++] = t.top();t.pop();}}if (strcmp(temp, M2) == 0) {for (int i = 0; i < strlen(ss); i++) {printf("%c ", ss[i]);  //注意格式为i 或 o 后面跟空格}putchar('\n');}}
}int main() {//freopen("D://in.txt", "r", stdin);while (scanf("%s", M) == 1) {int cur, curw;scanf("%s", M2);cout << "[\n";cur = 1;curw = 0;len = strlen(M);memset(ss, 0, sizeof(ss));T(cur, curw);cout << "]\n";}return 0;
}