【BZOJ1054】移动玩具（搜索）

题面

BZOJ

洛谷

题解

这种小清新搜索题写出来好舒服啊。

要是原来的我来写代码肯定又臭又长吧。。

#include<cstdio>

#include<queue>

using namespace std;

queue<int> Q;

int pw[16],st[1<<16];

bool vis[1<<16];

void add(int u,int v){if(vis[v])return;vis[v]=true;st[v]=st[u]+1;Q.push(v);}

int main()

{

	int S=0,x,T=0;

	for(int i=0;i<16;++i)pw[i]=1<<i;

	for(int i=0;i<16;++i)scanf("%1d",&x),S|=x<<i;

	for(int i=0;i<16;++i)scanf("%1d",&x),T|=x<<i;

	Q.push(S);vis[S]=true;

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		for(int i=0;i<16;++i)

		{

			if(!(u&pw[i]))continue;

			if(i>3&&!(u&pw[i-4]))add(u,u^pw[i-4]^pw[i]);

			if(i<12&&!(u&pw[i+4]))add(u,u^pw[i+4]^pw[i]);

			if(i%4&&!(u&pw[i-1]))add(u,u^pw[i-1]^pw[i]);

			if(i%4!=3&&!(u&pw[i+1]))add(u,u^pw[i+1]^pw[i]);

		}

		if(vis[T])break;

	}

	printf("%d\n",st[T]);

	return 0;

}