View Code of Problem 3799

#include <iostream>
#include <cstring>
#include <queue>

#define MAX 10010
#define ex(a) ((a+10)%10)
#define pos(a,b,c,d) (a*1000+b*100+c*10+d)

using namespace std;

int dp[MAX],vis[MAX],a[5];
int dfs[20][4]={{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1},{1,1,0,0},{0,1,1,0},{0,0,1,1},{1,1,1,0},{0,1,1,1},{1,1,1,1},{-1,0,0,0},{0,-1,0,0},{0,0,-1,0},{0,0,0,-1},{-1,-1,0,0},{0,-1,-1,0},{0,0,-1,-1},{-1,-1,-1,0},{0,-1,-1,-1},{-1,-1,-1,-1}};
queue<int> q;

int main()
{
	memset(vis,0,sizeof(vis));
	memset(dp,0,sizeof(dp));
	q.push(0);
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		for(int i=0,k=tmp;i<4;k/=10)a[i++]=k%10;
		for(int i=0;i<20;i++)
		{
			int p=pos(ex(a[3]+dfs[i][3]),ex(a[2]+dfs[i][2]),ex(a[1]+dfs[i][1]),ex(a[0]+dfs[i][0]));
			if(p==0)continue;
			if(dp[p]==0||dp[p]>(dp[tmp]+1))
			{
				dp[p]=(dp[tmp]+1);
				if(!vis[p])
				{
					vis[p]=1;
					q.push(p);
				}
			}

		}
		vis[tmp]=0;
	}
	
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int num[5],tmp;
		for(int i=0;i<4;scanf("%d",&num[i++]));
		for(int i=0;i<4;i++)
		{
			scanf("%d",&tmp);
			num[i]=ex(tmp-num[i]);
		}
		printf("%d\n",dp[pos(num[0],num[1],num[2],num[3])]);
	}
	return 0;
}

Double click to view unformatted code.


Back to problem 3799