1195 Open the Lock
http://acm.hdu.edu.cn/showproblem.php pid=1195
大致题意：给你两个四位数，一个作为开始一个作为目标，有三种操作每个位可以加1可以减1，可以与相邻的交换，都算一步，求转化到目标的最小步数
#include
#include
using namespace std;
char start[5], end[5];
int visited[10000];
struct node
{
char str[5];
int step;
};
void BFS()
{
queue Q;
node q;
strcpy(q.str, start);
q.step = 0;
Q.push(q);
while (!Q.empty())
{
q = Q.front();
Q.pop();
if(strcmp(q.str, end) == 0)
{
cout< return;
}
//+1
for (int i = 0; i<4; i++)
{
node p = q;
if (p.str[i] == '9') p.str[i] = '1';
else p.str[i] += 1;
p.step++;//加一步
int temp;
sscanf(p.str, "%d", &temp);
if (!visited[temp])
{
visited[temp] = 1;//标记
Q.push(p);
}
}
//-1
for (i = 0; i<4; i++)
{
node p = q;
if (p.str[i] == '1') p.str[i] = '9';
else p.str[i] -= 1;
p.step++;//加一步
int temp;
sscanf(p.str, "%d", &temp);
if (!visited[temp])
{
visited[temp] = 1;//标记
Q.push(p);
}
}
//exchange
for (i = 0; i<3; i++)
{
node p = q;
char t;
t = p.str[i];
p.str[i] = p.str[i + 1];
p.str[i + 1] = t;
p.step++;//加一步
int temp;
sscanf(p.str, "%d", &temp);
if (!visited[temp])
{
visited[temp] = 1;//标记
Q.push(p);
}
}
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>start>>end;
memset(visited, 0, sizeof(visited));
BFS();
}
return 0;
}
|