NKOJ 2498 （NOIP 2013）华容道（BFS+最短路）

发表于 |
字数统计: 1,785字 | 阅读时长 ≈ 8min

P2498【NOIP2013-D2T3】华容道

问题描述

小B最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面，华容道是否根本就无法完成，如果能完成，最少需要多少时间。
小B玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的：
1.在一个nm棋盘上有nm个格子，其中有且只有一个格子是空白的，其余nm-1个格子上每个格子上有一个棋子，每个棋子的大小都是11的；
2.有些棋子是固定的，有些棋子则是可以移动的；
3.任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。
游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

给定一个棋盘，游戏可以玩q次，当然，每次棋盘上固定的格子是不会变的，但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。
第i次玩的时候，空白的格子在第EXi行第EYi列，指定的可移动棋子的初始位置为第SXi行第SYi列，目标位置为第TXi行第TYi列。
假设小B每秒钟能进行一次移动棋子的操作，而其他操作的时间都可以忽略不计。
请你告诉小B每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。

输入格式

第一行有3个整数，每两个整数之间用一个空格隔开，依次表示n,m和q；
接下来的n行每行有 m 个整数，描述一个n*m的棋盘。每两个整数之间用一个空格隔开，每个整数描述棋盘上一个格子的状态，0表示该格子上的棋子是固定的，1表示该格子上的棋子可以移动或者该格子是空白的。
接下来的q行，每行包含6个整数依次是EXi,EYi,SXi,SYi,TXi,TYi,每两个整数之间用一个空格隔开，表示每次游戏空白格子的位置，指定棋子的初始位置和目标位置。

输出格式

输出有q行，每行包含1个整数，表示每次游戏所需要的最少时间，如果某次游戏无法完成目标则输出−1。

样例输入

3 4 2
0 1 1 1
0 1 1 0
0 1 0 0
3 2 1 2 2 2
1 2 2 2 3 2

样例输出

2
-1

此题一开始容易想到爆搜，及记录当前空白块的位置和起始块的位置，用（X1，Y1，X2，Y2）这个四元数组来记录状态直接搜，尝试发现只有30分。

观察移动的方式，可以发现如果要移动，那么需要移动的块和空白块必须相邻，于是我们可以改进一下我们的状态，用（X1，Y1，K）来表示，X1，Y1记录需要移动的块的位置，K表示空白块在该块的（上，下，左，右）四个位置。

于是我们可以用图论来解决，建边的时候讨论每一个点的4个状态分别移动到（上下左右）四个位置所需要的操作步数，这个用宽搜就可以实现，具体来讲，我们需要知道将空白块移动到目标位置，并且不经过需要移动的块所需的步数，连完边之后用最短路跑跑，跑4次最短路取达到终点的最短路径即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 12345
#define M 1234567
using namespace std;
//1 上 4 下 2 左 3 右 
struct node{int x,y,s;node(int a,int b,int c){x=a;y=b;s=c;}};
int n,m,q,map[32][32],id[32][32][5],tot,ans;
int ex,ey,sx,sy,tx,ty;
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
int TOT,LA[N],NE[M],EN[M],LE[M];
int dis[N];
queue<int>Q;
queue<node>P;
bool F[32][32],mark[N];
int GX(int x,int k)//找到对应位置的点坐标
{
	if(k==1)return x-1;
	if(k==4)return x+1;
	return x;
}
int GY(int y,int k)
{
	if(k==2)return y-1;
	if(k==3)return y+1;
	return y;
}
void ADD(int x,int y,int z)
{
	TOT++;
	EN[TOT]=y;
	LE[TOT]=z;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
int Find(int x1,int y1,int x2,int y2,int x,int y)
//找到从(x1,y1)到(x2,y2)的最短路径且不经过(x,y)
{
	if(x1==x2&&y1==y2)return 0;
	int i,j,k,xx,yy;
	memset(F,0,sizeof(F));
	while(P.size())P.pop();
	P.push(node(x1,y1,0));
	F[x1][y1]=1;
	while(!P.empty())
	{
		for(i=0;i<4;i++)
		{
			xx=P.front().x+dx[i];
			yy=P.front().y+dy[i];
			if(map[xx][yy]!=0&&(xx!=x||yy!=y))
			{
				if(xx==x2&&yy==y2)return P.front().s+1;
				if(F[xx][yy])continue;
				F[xx][yy]=1;
				P.push(node(xx,yy,P.front().s+1));
			}
		}
		P.pop();
	}
	return -1;
}
int SPFA(int u)
{
	int i,x,y;
	memset(dis,60,sizeof(dis));
	dis[u]=0;mark[u]=1;Q.push(u);
	while(Q.size())
	{
		x=Q.front();
		Q.pop();
		mark[x]=0;
		for(i=LA[x];i;i=NE[i])
		{
			y=EN[i];
			if(dis[y]>dis[x]+LE[i])
			{
				dis[y]=dis[x]+LE[i];
				if(!mark[y])mark[y]=1,Q.push(y);
			}
		}
	}
	int sum=dis[0];
	if(dis[id[tx][ty][1]]<sum)sum=dis[id[tx][ty][1]];
	if(dis[id[tx][ty][2]]<sum)sum=dis[id[tx][ty][2]];
	if(dis[id[tx][ty][3]]<sum)sum=dis[id[tx][ty][3]];
	if(dis[id[tx][ty][4]]<sum)sum=dis[id[tx][ty][4]];
	if(sum==dis[0])return -1;
	return sum;
}
int main()
{
	int i,j,k,p,x,y,z,x1,y1,x2,y2;
	scanf("%d%d%d",&n,&m,&q);
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)scanf("%d",&map[i][j]);
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	for(k=1;k<=4;k++)id[i][j][k]=++tot;
	
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	for(k=1;k<=4;k++)
	{
		x1=GX(i,k);y1=GY(j,k);
		if(map[i][j]==0||map[x1][y1]==0)continue;
	    for(p=0;p<4;p++)
	    {
	    	x=i+dx[p];
	    	y=j+dy[p];
	    	if(map[x][y]!=0)
	    	{
	    		if(x==x1&&y==y1)ADD(id[i][j][k],id[x][y][5-k],1);
	    		else
	    		{
	    			z=Find(x1,y1,x,y,i,j);
	    			if(z!=-1)ADD(id[i][j][k],id[x][y][4-p],z+1);
				}
			}
	    }
}

	while(q--)
	{
		scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
		if(sx==tx&&sy==ty){puts("0");continue;}//注意特判
		ans=1e9;
		for(i=1;i<=4;i++)
		{
			x=GX(sx,i);y=GY(sy,i);
			if(map[x][y]==0)continue;
			z=Find(ex,ey,x,y,sx,sy);
			if(z!=-1)
			{
				k=SPFA(id[sx][sy][i]);
				if(k!=-1)ans=min(ans,k+z);
			}
		}
		if(ans==1e9)puts("-1");
		else printf("%d\n",ans);
	}
}