洛谷 P1979 NOIp2013提高组 华容道 题解【最短路】【构造】
点击量：207
毒瘤图论建模题
题目描述
小B最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面， 华容道是否根本就无法完成，如果能完成， 最少需要多少时间。
小B玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的：
在一个$ n\times m$棋盘上有$ n\times m$个格子，其中有且只有一个格子是空白的，其余$ n\times m-1$个格子上每个格子上有一个棋子，每个棋子的大小都是$ 1\times 1$的；
- 有些棋子是固定的，有些棋子则是可以移动的；
- 任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。
- 游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。
给定一个棋盘，游戏可以玩$ q$次，当然，每次棋盘上固定的格子是不会变的， 但是棋盘上空白的格子的初始位置、 指定的可移动的棋子的初始位置和目标位置却可能不同。第$ i$次玩的时候， 空白的格子在第$ EX_i$行第$ EY_i$列，指定的可移动棋子的初始位置为第$ SX_i$行第$ SY_i$列，目标位置为第$ TX_i$行第$ TY_i$列。
假设小B每秒钟能进行一次移动棋子的操作，而其他操作的时间都可以忽略不计。请你告诉小B每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。
输入输出格式
输入格式：
第一行有3个整数，每两个整数之间用一个空格隔开，依次表示$ n,m,q$；
接下来的$ n$行描述一个$ n \times m$的棋盘，每行有$ m$个整数，每两个整数之间用一个空格隔开，每个整数描述棋盘上一个格子的状态，0表示该格子上的棋子是固定的，1表示该格子上的棋子可以移动或者该格子是空白的。
接下来的$ q$行，每行包含6个整数依次是$ EX_i,EY_i,SX_i,SY_i,TX_i,TY_i$，每两个整数之间用一个空格隔开，表示每次游戏空白格子的位置，指定棋子的初始位置和目标位置。
输出格式：
共$ q$行，每行包含1个整数，表示每次游戏所需要的最少时间，如果某次游戏无法完成目标则输出-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输出样例#1：
2 -1说明
【输入输出样例说明】
棋盘上划叉的格子是固定的，红色格子是目标位置，圆圈表示棋子，其中绿色圆圈表示目标棋子。
1.第一次游戏，空白格子的初始位置是(3,2)（图中空白所示），游戏的目标是将初始位置在(1,2) 上的棋子（图中绿色圆圈所代表的棋子）移动到目标位置(2,2)（图中红色的格子）上。
移动过程如下：
2.第二次游戏，空白格子的初始位置是(1,2) （图中空白所示），游戏的目标是将初始位置在(2,2)上的棋子（图中绿色圆圈所示）移动到目标位置(3,2)上。
要将指定块移入目标位置，必须先将空白块移入目标位置，空白块要移动到目标位置，必然是从位置 (2,2)(2,2) 上与当前图中目标位置上的棋子交换位置，之后能与空白块交换位置的只有当前图中目标位置上的那个棋子，因此目标棋子永远无法走到它的目标位置， 游戏无法完成。
【数据范围】
对于$ 30\%$的数据，$ 1\le n,m\le 10,q=1$；
对于$ 60\%$的数据，$ 1\le n,m\le 30,q\le 10$；
对于$ 100\%$的数据，$ 1\le n,m\le 30,q\le 500$。
题解：
棋盘上棋子的移动实则是空白块的移动。而空白块有四个方向可以移动，每次只用更改两个位置的状态就可以了，当访问到初始方块的状态时，改变初始状态的位置。当初始状态与目标状态重合时，停止搜索。因此保存初始方块和空格的位置，用used判断这个四元组是否被访问过，没有被访问过就进队。时间复杂度$ O(qn^2m^2)$，当$ q$很大时会超时。期望得分70’。
而在上面的搜索中，棋盘上的空格就算变来变去，转不到初始方块旁边就什么用也没有。因此我们可以预处理出空格到每个点的距离，在询问时直接调用初始方块周边的点为空格的状态时要走多少步。但是空格挪过来了仍然要搜索啊，此时我们如果仍然只关注初始方块周围的空格，就会发现，挪动一格后，就无路可走了，又需要移动空格。如果我们每次bfs的话，时间复杂度比上述搜索还慢。而如果用图论的方法预处理出各点之间的距离，不仅要求不经过当前初始点的位置，而且复杂度会更高。
但是在解题思路中我们发现几乎所有的状态都是空格和初始状态连接在一起的，我们是不是可以把初始方块各个方向的空格相互转移的步数给预处理出来，这样搜索时直接调用就可以了。同样地，初始方块移动后，也和空格连接在一起。因此，除了把空格移到初始方块旁边，所有状态都可以用初始方块与空格相连的情况来表示，一共是$ 4nm$种。而$ nm$的上界是900，那么有3600种情况，初始状态可能有4种，最终状态可能有4种。所以我们可以在这些状态之间建个图，跑4次单源最短路径，与一开始移动空格的步数加起来，求出最小值就是答案了。
所以我们还要预处理出一个初始方块四个方向有空格互相之间的距离，把一个初始方块的位置拆成四个点，互相连边。为了保证图的连通性，初始方块与空格交换位置也连一条边，边权为1。
所有状态转移一定要注意a[x][y]==1。注意枚举方向时点的编号要注意方向。在每次bfs时当前初始方块的位置是不能变的。
Code：
#include<cstdio>
#include<cstring>
#include<queue>
using std::priority_queue;
struct edge
{
int n,v;
int nxt;
edge(int n,int v,int nxt)
{
this->n=n;
this->v=v;
this->nxt=nxt;
}
edge(){nxt=-1;}
}e[100000];
int head[4000],ecnt=-1;
void add(int from,int to,int v)
{
e[++ecnt]=edge(to,v,head[from]);
head[from]=ecnt;
e[++ecnt]=edge(from,v,head[to]);
head[to]=ecnt;
}
int n,m;
int turn(int x,int y)
{
return 4*((x-1)*m+y-1);
}
int x[6]={0,-1,0,1,0};//方向的规律
int y[6]={0,0,1,0,-1};
int dis[4000];
struct statu
{
int n,dis;
friend bool operator <(statu a,statu b)
{
return a.dis>b.dis;
}
statu(int n,int dis)
{
this->n=n;
this->dis=dis;
}
};
void dijk(int from)
{
priority_queue<statu> q;
memset(dis,0x3f,sizeof(dis));
q.push(statu(from,0));
dis[from]=0;
while(!q.empty())
{
statu k=q.top();
q.pop();
if(dis[k.n]<k.dis)
continue;
for(int i=head[k.n];~i;i=e[i].nxt)
if(dis[e[i].n]>dis[k.n]+e[i].v)
{
dis[e[i].n]=dis[k.n]+e[i].v;
q.push(statu(e[i].n,dis[e[i].n]));
}
}
return;
}
int a[33][33];
int bfs(int sx,int sy,int tx,int ty,int nx,int ny)//nx,ny是不能走的
{
if(sx==tx&&sy==ty)
return 0;
int X[4444],l=0,r=0,now;
int Y[4444],k[4444];
int used[33][33];
memset(used,0,sizeof(used));
X[++r]=sx;
Y[r]=sy;
k[r]=0;
used[sx][sy]=1;
while(l<r)
{
sx=X[++l];
sy=Y[l];
now=k[l];
for(int i=1;i<=4;i++)
if((sx+x[i]!=nx||sy+y[i]!=ny)&&a[sx+x[i]][sy+y[i]]&&!used[sx+x[i]][sy+y[i]])
{
used[sx+x[i]][sy+y[i]]=1;
if(sx+x[i]==tx&&sy+y[i]==ty)
return now+1;
X[++r]=sx+x[i];
Y[r]=sy+y[i];
k[r]=now+1;
}
}
return -1;
}
int main()
{
memset(head,-1,sizeof(head));
int T;
scanf("%d%d%d",&n,&m,&T);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j])
{
int pla=turn(i,j);
if(a[i-1][j]&&a[i][j+1])
{
int l=bfs(i-1,j,i,j+1,i,j);
if(l!=-1)
add(pla+1,pla+2,l);
}
if(a[i][j+1]&&a[i+1][j])
{
int l=bfs(i,j+1,i+1,j,i,j);
if(l!=-1)
add(pla+2,pla+3,l);
}
if(a[i+1][j]&&a[i][j-1])
{
int l=bfs(i+1,j,i,j-1,i,j);
if(l!=-1)
add(pla+3,pla+4,l);
}
if(a[i][j-1]&&a[i-1][j])
{
int l=bfs(i,j-1,i-1,j,i,j);
if(l!=-1)
add(pla+4,pla+1,l);
}
if(a[i][j+1]&&a[i][j-1])
{
int l=bfs(i,j-1,i,j+1,i,j);
if(l!=-1)
add(pla+2,pla+4,l);
}
if(a[i-1][j]&&a[i+1][j])
{
int l=bfs(i-1,j,i+1,j,i,j);
if(l!=-1)
add(pla+1,pla+3,l);
}
if(a[i][j+1])
add(pla+2,pla+8,1);
if(a[i+1][j])
add(pla+3,pla+4*m+1,1);
}
while(T--)
{
int ex,ey,sx,sy,tx,ty,ans1=99999999;
scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
if(sx==tx&&sy==ty)//这种情况卡了35分
{
puts("0");
continue;
}
for(int i=1;i<=4;i++)
{
int sum=bfs(ex,ey,sx+x[i],sy+y[i],sx,sy);
if(sum==-1)
continue;
dijk(turn(sx,sy)+i);
int ans=0x3fffffff;
for(int j=1;j<=4;j++)
{
int t=dis[turn(tx,ty)+j];
ans=ans<t?ans:t;
}
ans1=ans1<sum+ans?ans1:sum+ans;
}
printf("%d\n",ans1==99999999?-1:ans1);
}
return 0;
}
说点什么