搜索系列――Anagram（全排列） (二)

结果，剪枝剪了半天剪不了，果然我太弱了。。。

参考网上的解题报告，发现好多都是用的C++里面的stl里面的next_permutation函数，找到一个dfs的，照着剪枝，提交后老超时，我还以为是我手工排序比sort慢，又改又超时，改了几次之后越来越像人家的代码，后来干脆把他的代码贴上去，也是超时！

好坑！

剪枝后代码如下（未AC）：

[cpp]
#include
#include

float val[13];
int num, res[13], visited[13];
char ch[13];

void dfs(int cur)
{
if (cur == num)
{
for (int i = 0; i < num; i++)
printf("%c", ch[res[i]]);
printf("\n");
return;
}
for (int i = 0; i < num; i++)
if (!visited[i])
{
res[cur] = i;
visited[i] = 1;
dfs(cur + 1);
visited[i] = 0;
while(i + 1 < num && val[i] == val[i + 1])
i++;
}
}

int main()
{
int n;
num = 0;
scanf("%d", &n);
while (n--)
{
memset(visited, 0, sizeof(visited));
num = 0;
scanf("%s", ch);
for (int i = 0; ch[i] != '\0'; i++)
{
num++;
if (ch[i] >= 'A'&& ch[i] <= 'Z')
val[i] = ch[i] - 'A';
else
val[i] = ch[i] - 'a' + 0.5;
}
for (int i = 0; i < num; i++) //sort
for (int j = i + 1; j < num; j++)
if (val[i] > val[j])
{
float e = val[i];
val[i] = val[j];
val[j] = e;
char t = ch[i];
ch[i] = ch[j];
ch[j] = t;
}
dfs(0);
}
return 0;
}

#include
#include

float val[13];
int num, res[13], visited[13];
char ch[13];

void dfs(int cur)
{
if (cur == num)
{
for (int i = 0; i < num; i++)
printf("%c", ch[res[i]]);
printf("\n");
return;
}
for (int i = 0; i < num; i++)
if (!visited[i])
{
res[cur] = i;
visited[i] = 1;
dfs(cur + 1);
visited[i] = 0;
while(i + 1 < num && val[i] == val[i + 1])
i++;
}
}

int main()
{
int n;
num = 0;
scanf("%d", &n);
while (n--)
{
memset(visited, 0, sizeof(visited));
num = 0;
scanf("%s", ch);
for (int i = 0; ch[i] != '\0'; i++)
{
num++;
if (ch[i] >= 'A'&& ch[i] <= 'Z')
val[i] = ch[i] - 'A';
else
val[i] = ch[i] - 'a' + 0.5;
}
for (int i = 0; i < num; i++) //sort
for (int j = i + 1; j < num; j++)
if (val[i] > val[j])
{
float e = val[i];
val[i] = val[j];
val[j] = e;
char t = ch[i];
ch[i] = ch[j];
ch[j] = t;
}
dfs(0);
}
return 0;
}

我决定用STL了。。。

代码如下（已A）：

[cpp]
#include
#include
#include
#include
using namespace std;

bool cmp(char a, char b)
{
double t1 = a, t2 = b;
if (a >= 'A' && a <= 'Z')
t1 += 31.5;
if (b >= 'A' && b <= 'Z')
t2 += 31.5;
return t1 < t2;
}

int main()
{
int n, len;
char str[15];
cin >> n;
while(n--)
{
cin >> str;
len = strlen(str);
sort(str, str + len, cmp);
do
{
cout << str << endl;
}
while(next_permutation(str, str + len, cmp));
}
return 0;
}

#include
#include
#include
#include
using namespace std;

bool cmp(char a, char b)
{
double t1 = a, t2 = b;
if (a >= 'A' && a <= 'Z')
t1 += 31.5;
if (b >= 'A' && b <= 'Z')
t2 += 31.5;
return t1 < t2;
}

int main()
{
int n, len;
char str[15];
cin >> n;
while(n--)
{
cin >> str;
len = strlen(str);
sort(str, str + len, cmp);
do
{
cout << str << endl;
}
while(next_permutation(str, str + len, cmp));
}
return 0;
}