题意：求出将上面的数字变成下面的数字所需的最少路数。变换方式只有“加”，“减”，“交换”三种。
一道很普通的广搜题。用used[]记录各节点的层数，以及判断该结点是否被访问过（used[i] == 0 表示没有访问过。特别注意初始节点的层数为0，但它被访问过，因此要特殊处理一下。）
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 10010
#include<queue>
using namespace std;
char Add(char a)
{
if(a == '9')
return '1';
else
return a + 1;
}
char Sub(char a)
{
if(a == '1')
return '9';
else
return a - 1;
}
int StrToNum(char * s)
{
int len = strlen(s);
int i;
int sum = 0;
for(i = 0; i < len; i++)
{
sum = sum * 10 + s[i] - '0';
}
return sum;
}
int used[LEN];
int main()
{
int i, j;
int T;
int find;
char N[6], M[6], t[6];
queue<char*> q;
scanf("%d", &T);
for(i = 0; i < T; i++)
{
scanf("%s", N);
scanf("%s", M);
find = 0;
for(j = 0; j < LEN; j++)
used[j] = 0;
q.push(N);
if(strcmp(N, M) == 0)
find = 1;
used[StrToNum(N)] = 1;
while(!find)
{
strcpy(t, q.front());
q.pop();
int tn0 = StrToNum(t);
for(j = 0; j < 4 && !find; j++)
{
char *t2 = (char*)malloc(sizeof(char) * 6);
strcpy(t2, t);
t2[j] = Add(t2[j]);
int tn = StrToNum(t2);
if(strcmp(t2, M) == 0)
{
find = 1;
used[tn] = used[tn0] + 1;
free(t2);
}
else if(!used[tn])
{
q.push(t2);
used[tn] = used[tn0] + 1;
}
else
free(t2);
}
for(j = 0; j < 4 && !find; j++)
{
char *t2 = (char*)malloc(sizeof(char) * 6);
strcpy(t2, t);
t2[j] = Sub(t2[j]);
int tn = StrToNum(t2);
if(strcmp(t2, M) == 0)
{
find = 1;
used[tn] = used[tn0] + 1;
free(t2);
}
else if(!used[tn])
{
q.push(t2);
used[tn] = used[tn0] + 1;
}
else
free(t2);
}
for(j = 0; j < 3 && !find; j++)
{
char *t2 = (char*)malloc(sizeof(char) * 6);
strcpy(t2, t);
char ct = t2[j];
t2[j] = t2[j + 1];
t2[j + 1] = ct;
int tn = StrToNum(t2);
if(strcmp(t2, M) == 0)
{
find = 1;
used[tn] = used[tn0] + 1;
free(t2);
}
else if(!used[tn])
{
q.push(t2);
used[tn] = used[tn0] + 1;
}
else
free(t2);
}
}
while(!q.empty())
{
//free(q.front());
q.pop();
}
printf("%d\n", used[StrToNum(M)] - 1);
}
return 0;
}posted on 2012-03-29 00:02
小鼠标 阅读(161)
评论(0) 编辑 收藏 引用