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;
}
更多推荐
ZOJ Problem Set - 1004(回溯法)
发布评论