【bzoj1054】[HAOI2008]移动玩具

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int q[70000] , l , r , f[70000];
char str[10];
int read()
{
	int i , j , num = 0 , b = 1;
	for(i = 0 ; i < 4 ; i ++ )
	{
		scanf("%s" , str);
		for(j = 0 ; j < 4 ; j ++ )
			num += (str[j] - ‘0‘) * b , b <<= 1;
	}
	return num;
}
int main()
{
	int a , b , u , v , i;
	a = read() , b = read();
	memset(f , -1 , sizeof(f));
	q[0] = a;
	f[a] = 0;
	while(l <= r)
	{
		u = q[l ++ ];
		if(u == b)
		{
			printf("%d\n" , f[u]);
			return 0;
		}
		for(i = 1 ; i <= 16 ; i ++ )
		{
			if(u & (1 << (i - 1)))
			{
				v = u ^ (1 << (i - 1));
				if(i > 4 && (~v) & (1 << (i - 5)) && f[v ^ (1 << (i - 5))] == -1)
					f[v ^ (1 << (i - 5))] = f[u] + 1 , q[++r] = v ^ (1 << (i - 5));
				if(i < 13 && (~v) & (1 << (i + 3)) && f[v ^ (1 << (i + 3))] == -1)
					f[v ^ (1 << (i + 3))] = f[u] + 1 , q[++r] = v ^ (1 << (i + 3));
				if((i - 1) % 4 && (~v) & (1 << (i - 2)) && f[v ^ (1 << (i - 2))] == -1)
					f[v ^ (1 << (i - 2))] = f[u] + 1 , q[++r] = v ^ (1 << (i - 2));
				if(i % 4 && (~v) & (1 << i) && f[v ^ (1 << i)] == -1)
					f[v ^ (1 << i)] = f[u] + 1 , q[++r] = v ^ (1 << i);
			}
		}
	}
	return 0;
}