分析

这道题很容易想到令f[x][y][x1][y1]表示空白块在(x,y)、指定棋子在(x1,y1)时的最少步数，让空白块和四周的棋子交换，当空白块要和指定棋子交换时，把指定棋子移动，搞一下BFS就可以了，时间复杂度O(qn^2m2),可以拿60+。

因为只有空白块在指定棋子的旁边，指定棋子才能移动，而且指定棋子每次移动后，空白块仍然与指定棋子相邻。所以令move[x][y][k][l]表示指定棋子在(x,y)，空白块在与指定棋子相邻的k方向，要将空白块移动到与指定棋子相邻的l方向需要的步数。那么首先把move预处理出来，在每一次讯问中，把空白格移到指定棋子相邻的存在的格子，做一次spfa，就可以了。

spfa：令f[x][y][k]表示指定棋子在(x,y)，空白块在与指定棋子相邻的k方向的状态需要的最少步数。转移显然，(xx,yy)是要移动到的方向，i表示指定格子要向i方向走，k1指移动后空白块在与指定棋子相邻的k方向，k1即是i的相反方向，那么f[x][y][k]+move[x][y][k][i]+1==>f[xx][yy][k1]。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

using namespace std;

int n,m,qu,a[40][40]={0},z[4][2]={{0,1},{1,0},{0,-1},{-1,0}},d[1000000][5],move[31][31][5][5],f[31][31][5];

int d1[1000000][5],xx,yy;

bool bz[31][31],b[31][31][5];

int bfs(int x,int y,int k1,int k2)

{

	int i,j,k,l,head=0,tail=1,x1=z[k1][0]+x,y1=z[k1][1]+y,x2=z[k2][0]+x,y2=z[k2][1]+y;

	int xx,yy;

	if(!a[x1][y1] || !a[x2][y2]) return 0;

	memset(bz,true,sizeof(bz));

	bz[x][y]=false;

	d[1][0]=0;

	d[1][1]=x1;

	d[1][2]=y1;

	bz[x1][y1]=false;

	while(head<tail)

	{

		k=++head;

		for(i=0;i<=3;i++)

		{

			xx=d[k][1]+z[i][0];

			yy=d[k][2]+z[i][1];

			if(bz[xx][yy] && a[xx][yy])

			{

				d[++tail][0]=d[k][0]+1;

				d[tail][1]=xx;

				d[tail][2]=yy;

				bz[xx][yy]=false;

				if(xx==x2 && yy==y2)

				{

					move[x][y][k1][k2]=d[tail][0];

					return 0;

				}

			}

		}

	}

	return 0;

}

int bk(int x,int y,int x1,int y1)

{

	memset(bz,true,sizeof(bz));

	d1[0][0]=0;

	bz[x][y]=false;

	bz[x1][y1]=false;

	d[1][0]=0;

	d[1][1]=x;

	d[1][2]=y;

	int head=0,tail=1,i,j,k;

	while(head<tail)

	{

		k=++head;

		for(i=0;i<=3;i++)

		{

			xx=d[k][1]+z[i][0];

			yy=d[k][2]+z[i][1];

			if(bz[xx][yy] && a[xx][yy])

			{

				d[++tail][0]=d[k][0]+1;

				d[tail][1]=xx;

				d[tail][2]=yy;

				bz[xx][yy]=false;

			}

			else

			if(xx==x1 && yy==y1)

			{

				d1[++d1[0][0]][0]=d[k][0];

				d1[d1[0][0]][1]=xx;

				d1[d1[0][0]][2]=yy;

				d1[d1[0][0]][3]=(i+2)%4;

			}

		}

	}

}

int pre()

{

	memset(move,43,sizeof(move));

	int i,j,k,l;

	for(i=1;i<=n;i++)

		for(j=1;j<=m;j++)

			if(a[i][j])

				for(k=0;k<=3;k++)

					for(l=0;l<=3;l++)

					{

						if(k==l)

						{

							move[i][j][k][l]=0;

						}

						else bfs(i,j,k,l);

					}

	return 0;

}

int spfa()

{

	int i,j,k,l,head=0,tail=d1[0][0];

	memset(b,true,sizeof(b));

	for(i=1;i<=d1[0][0];i++)

	{

		f[d1[i][1]][d1[i][2]][d1[i][3]]=d1[i][0];

		b[d1[i][1]][d1[i][2]][d1[i][3]]=false;

	}

	while(head<tail)

	{

		k=++head;

		b[d1[k][1]][d1[k][2]][d1[k][3]]=true;

		for(i=0;i<=3;i++)

		{

			xx=d1[k][1]+z[i][0];

			yy=d1[k][2]+z[i][1];

			if(f[d1[k][1]][d1[k][2]][d1[k][3]]+move[d1[k][1]][d1[k][2]][d1[k][3]][i]+1<f[xx][yy][(i+2)%4])

			{

				f[xx][yy][(i+2)%4]=f[d1[k][1]][d1[k][2]][d1[k][3]]+move[d1[k][1]][d1[k][2]][d1[k][3]][i]+1;

				if(b[xx][yy][(i+2)%4])

				{

					b[xx][yy][(i+2)%4]=false;

					d1[++tail][1]=xx;

					d1[tail][2]=yy;

					d1[tail][3]=(i+2)%4;

				}

			}

		}

	}

}

int main()

{

	scanf("%d%d%d",&n,&m,&qu);

	int i,j,k,l;

	for(i=1;i<=n;i++)

		for(j=1;j<=m;j++)

			scanf("%d",&a[i][j]);

	int p=-1;

	pre();

	while(qu--)

	{

		int x,y,x1,y1,x2,y2,head=0,tail=1,xx,yy;

		scanf("%d%d%d%d%d%d",&x,&y,&x1,&y1,&x2,&y2);

		bk(x,y,x1,y1);

		if(x2==x1 && y2==y1)

		{

			printf("0\n");

		}

		else

		{

			memset(f,43,sizeof(f));

			int ans=f[0][0][0];

			spfa();

			for(i=0;i<=3;i++)

				ans=min(ans,f[x2][y2][i]);

			if(ans==f[0][0][0]) printf("-1\n");

				else printf("%d\n",ans);

		}

	}

}

巴特西

【华容道】题解（NOIP2013提高组day2）

分析

最新文章

热门文章