題意：求出將上面的數字變成下面的數字所需的最少路數。變換方式只有“加”，“減”，“交換”三種。
一道很普通的廣搜題。用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
小鼠標 閱讀(187)
評論(0) 編輯 收藏 引用