Flandre Scarlet's Blog

自古T6码农题【雾】自古六面出忠臣!

奇葩改编华容道（更TM像八数码好么）

初始思路：大力BFS！（考虑只需要记录空格与需移动点的状态）

目测60分，TLE（其实我并没有写过，SHC神犇说可以加个启发式或是双向【双向A*BFS】；老板娘说可以随机化模拟退火）

因为可移动棋子一定要空格在边上才能动，所以肯定先要做一个最短路从空格到棋子，然后空格滚到棋子的另一边才能移动。

关键是q次询问都在同一个图里！

预处理预处理？预处理预处理！

以空格靠在棋子某个方向为状态点，构图。算出每个点相邻四格互相移动的步数，连边。空格和棋子交换（即棋子挪动）也连边，权为1。

以超级起点（初始空格）跑到棋子四周的距离连边，目标终点四周与超级终点连边，边权为0，跑最短路。

Code似乎写得长了点QAQ

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define maxv 32
#define maxn 3600
#define maxm 30000
#define INF 2000000000
using namespace std;
struct Edge
{
	int fr,to,d;
};
struct poi
{
	int x,y;
};
int ST[4][2]={{0,-1},{-1,0},{1,0},{0,1}};
int a[maxv][maxv],r,c,q;//row,column
int dir[maxv][maxv][4];//上下左右点号
int GO[maxv][maxv][4][4];
int b[maxv][maxv];
//0-L,1-U,2-D,3-R
queue <poi> Q;
int dd[maxv][maxv];
void BFS2(poi S,int* ans,int xx,int yy)//空格从某方向移至另一方向
{
	memset(b,0,sizeof(b));
	
	Q.push(S);
	b[S.x][S.y]=1;
	for (int i=0;i<=r+1;i++)
		for (int j=0;j<=c+1;j++)
			dd[i][j]=INF;
	dd[S.x][S.y]=0;
	poi n;
	while (!Q.empty())
	{
		n=Q.front();
		Q.pop();
		for (int i=0;i<4;i++)
		{
			int x=n.x+ST[i][0],y=n.y+ST[i][1];
			if (!a[x][y]) continue;
			if (b[x][y]) continue;
			Q.push((poi){x,y});
			b[n.x][n.y]=1;
			dd[x][y]=dd[n.x][n.y]+1;
		}
	}
	for (int i=0;i<4;i++)
		ans[i]=dd[xx+ST[i][0]][yy+ST[i][1]];
}
int n=0,m=0;
Edge es[maxm];
int next[maxm],first[maxn],dis[maxn],inq[maxn],ww[4];
queue <int> S;
void AddEdge(int f,int t,int w)
{
	m++;
	es[m]=(Edge){f,t,w};
	next[m]=first[f];
	first[f]=m;
}
void DelEdge(int f)
{
	first[f]=next[first[f]];
	m--;
}
int SPFA(int s,int t)
{
	for (int i=0;i<=n;i++)
		dis[i]=INF;
	dis[s]=0;
	S.push(s);
	inq[s]=1;
	while (!S.empty())
	{
		int u=S.front();
		S.pop();
		inq[u]=0;
		for (int i=first[u];i!=-1;i=next[i])
		{
			Edge e=es[i];
			if (dis[e.to]>dis[u]+e.d)
			{
				dis[e.to]=dis[u]+e.d;
				if (!inq[e.to])
				{
					inq[e.to]=1;
					S.push(e.to);
				}
			}
		}
	}
	if (dis[n]==INF) return -1;
	return dis[n];
}
int main()
{
	scanf("%d%d%d",&r,&c,&q);
	for (int i=1;i<=r;i++)
		for (int j=1;j<=c;j++)
			scanf("%d",&a[i][j]);
	for (int i=1;i<=r;i++)
		for (int j=1;j<=c;j++)
		{
			if (!a[i][j]) continue;
			for (int k=0;k<4;k++)
			{
				int x=i+ST[k][0],y=j+ST[k][1];
				if (!a[x][y]) continue;
				dir[i][j][k]=++n;
			}
		}
	for (int i=1;i<=r;i++)
		for (int j=1;j<=c;j++)
			if (a[i][j])	
			{
				a[i][j]=0;
				for (int k=0;k<4;k++)
					if (dir[i][j][k])
					{
						BFS2((poi){i+ST[k][0],j+ST[k][1]},ww,i,j);
						for (int l=0;l<4;l++)
							GO[i][j][k][l]=ww[l];
					}
				a[i][j]=1;	
			}
	n++;//0:Start n+1:Terminal
	for (int i=0;i<=n;i++)
		first[i]=-1;
	for (int i=1;i<=r;i++)
		for (int j=1;j<=c;j++)
		{
			if (!a[i][j]) continue;
			for (int k=0;k<4;k++)
			{
				int x=i+ST[k][0],y=j+ST[k][1];
				if (!a[x][y]) continue;
				AddEdge(dir[i][j][k],dir[x][y][3-k],1);
			}
		}
	for (int i=1;i<=r;i++)
		for (int j=1;j<=c;j++)
			if (a[i][j])
				for (int k=0;k<4;k++)
					if (dir[i][j][k])
						for (int l=0;l<4;l++)
							if (dir[i][j][l])
								if (k!=l) 
									if (GO[i][j][k][l]!=INF)
										AddEdge(dir[i][j][k],dir[i][j][l],GO[i][j][k][l]);
	for (int i=1;i<=q;i++)
	{
		int Ex,Ey,Sx,Sy,Tx,Ty;
		scanf("%d%d%d%d%d%d",&Ex,&Ey,&Sx,&Sy,&Tx,&Ty);
		if (!(a[Sx][Sy]&&a[Tx][Ty])) 
		{
			printf ("-1\n");
			continue;
		} 
		if (Ex==Sx&&Ey==Sy)
		{
			printf ("-1\n");
			continue;
		} 
		if (Tx==Sx&&Ty==Sy)
		{
			printf("0\n");
			continue;
		} 
		a[Sx][Sy]=0;
		BFS2((poi){Ex,Ey},ww,Sx,Sy);
		a[Sx][Sy]=1;
		
		for (int k=0;k<4;k++)
			if (dir[Sx][Sy][k]) AddEdge(0,dir[Sx][Sy][k],ww[k]);
		for (int k=0;k<4;k++)
			if (dir[Tx][Ty][k]) AddEdge(dir[Tx][Ty][k],n,0);
		printf("%d\n",SPFA(0,n));
		for (int k=3;k>=0;k--)
			if (dir[Tx][Ty][k]) DelEdge(dir[Tx][Ty][k]);
		for (int k=3;k>=0;k--)
			if (dir[Sx][Sy][k]) DelEdge(0);
		
	}
	return 0;
}

祝贺CCF在IOI上被打脸*1，OI目前起源于韩国。