NYOI P3631 密码锁

Coros_Trusds

问题描述
何老板的密码锁由四位数字组成，每个数字的范围在1到9之间。
现在何老板告诉你开锁的密码，问，你最少需要多少步才能打开锁。

每一步，你可以进行下列三种操作：
1.向上转动密码盘，使一个数字加1(数字9再加1会变为1)；
2.向下转动密码盘，使一个数字减1(数字1再减1会变为9)；
3.交换两个相邻的数字(交换相邻两个密码盘，比如数字1357,交换左起第一和第二个密码盘后，得到3157)

输入格式
第一行，4个数字，表示锁当前的状态
第二行，4个数字，表示开锁的密码

输出格式
一个整数，表示打开锁需要的最少步数

思路+分析
考虑尝试BFS。
分类讨论加一、减一和交换数字的情况，简单模拟即可。


#include <cstdio>

#include <queue>

using namespace std;

int n,m,ans,a[10][10][10][10],b[5];

struct Node
{
	int c[5];
	
	int step;
};

queue<Node>q;

int main()
{
    for(int i=1;i<=4;i++)
    {
    	scanf("%d",&b[i]);
	}
	
	Node node;
	
	for(int i=1;i<=4;i++)
	{
		scanf("%d",&node.c[i]);
	}
	//BFS
	node.step=0;
	
	q.push(node);
	
	while(!q.empty())
	{
		Node nodee=q.front();
		
		q.pop();
		
		for(register int i=1;i<=4;i++)
		{
		//加一
			node=nodee;
			
			if(nodee.c[i]<9)
			{
				node.c[i]=nodee.c[i]+1;
			}
			
			else
			{
				node.c[i]=1;
			}
			
			node.step=nodee.step+1;
			
		    if(node.c[1]==b[1] && node.c[2]==b[2] && node.c[3]==b[3] && node.c[4]==b[4])
		    {
		    	printf("%d",node.step);
		    	
		    	return 0;
			}
			
			if(a[node.c[1]][node.c[2]][node.c[3]][node.c[4]]==0)
			{
				q.push(node);
				
				a[node.c[1]][node.c[2]][node.c[3]][node.c[4]]=1;
			}
			//减一
			if(nodee.c[i]>1)
			{
				node.c[i]=nodee.c[i]-1;
			}
			
			else
			{
				node.c[i]=9;
			}
			
			node.step=nodee.step+1;
			
			if(node.c[1]==b[1] && node.c[2]==b[2] && node.c[3]==b[3] && node.c[4]==b[4])
		    {
		    	printf("%d",node.step);
		    	
		    	return 0;
			}
			
			if(a[node.c[1]][node.c[2]][node.c[3]][node.c[4]]==0)
			{
				q.push(node);
				
				a[node.c[1]][node.c[2]][node.c[3]][node.c[4]]=1;
			}
		}
	    //交换两个数
		for(register int j=1;j<=3;j++)//可能是1与2  2与3  3与4，共三种情况
		{
			node=nodee;
			
			node.c[j]^=node.c[j+1];
			
			node.c[j+1]^=node.c[j];
			
			node.c[j]^=node.c[j+1];
			//等价于swap(node.c[j],node.c[j+1];
			
			node.step++;
			
			if(node.c[1]==b[1] && node.c[2]==b[2] && node.c[3]==b[3] && node.c[4]==b[4])
		    {
		    	printf("%d",node.step);
		    	
		    	return 0;
			}
			
			if(a[node.c[1]][node.c[2]][node.c[3]][node.c[4]]==0)
			{
				q.push(node);
				
				a[node.c[1]][node.c[2]][node.c[3]][node.c[4]]=1;
			}
		}
	}
}