P1979 华容道
题目描述
【问题描述】
小 B 最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面， 华容道是否根本就无法完成，如果能完成， 最少需要多少时间。
小 B 玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的：
-
在一个 n*m 棋盘上有 n*m 个格子，其中有且只有一个格子是空白的，其余 n*m-1个格子上每个格子上有一个棋子，每个棋子的大小都是 1*1 的；
-
有些棋子是固定的，有些棋子则是可以移动的；
- 任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。
游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。
给定一个棋盘，游戏可以玩 q 次，当然，每次棋盘上固定的格子是不会变的， 但是棋盘上空白的格子的初始位置、 指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次
玩的时候， 空白的格子在第 EXi 行第 EYi 列，指定的可移动棋子的初始位置为第 SXi 行第 SYi列，目标位置为第 TXi 行第 TYi 列。
假设小 B 每秒钟能进行一次移动棋子的操作，而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。
输入输出格式
输入格式：输入文件为 puzzle.in。
第一行有 3 个整数，每两个整数之间用一个空格隔开，依次表示 n、m 和 q；
接下来的 n 行描述一个 n*m 的棋盘，每行有 m 个整数，每两个整数之间用一个空格隔开，每个整数描述棋盘上一个格子的状态，0 表示该格子上的棋子是固定的，1 表示该格子上的棋子可以移动或者该格子是空白的。接下来的 q 行，每行包含 6 个整数依次是 EXi、EYi、SXi、SYi、TXi、TYi，每两个整数之间用一个空格隔开，表示每次游戏空白格子的位置，指定棋子的初始位置和目标位置。
输出格式：输出文件名为 puzzle.out。
输出有 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
说明
【输入输出样例说明】
棋盘上划叉的格子是固定的，红色格子是目标位置，圆圈表示棋子，其中绿色圆圈表示目标棋子。
- 第一次游戏，空白格子的初始位置是 (3, 2)（图中空白所示），游戏的目标是将初始位置在(1, 2)上的棋子（图中绿色圆圈所代表的棋子）移动到目标位置(2, 2)（图中红色的格子）上。
移动过程如下：
- 第二次游戏，空白格子的初始位置是（1, 2）（图中空白所示），游戏的目标是将初始位置在（2, 2）上的棋子（图中绿色圆圈所示）移动到目标位置 (3, 2)上。
要将指定块移入目标位置，必须先将空白块移入目标位置，空白块要移动到目标位置，必然是从位置（2， 2）上与当前图中目标位置上的棋子交换位置，之后能与空白块交换位置的只有当前图中目标位置上的那个棋子，因此目标棋子永远无法走到它的目标位置， 游戏无
法完成。
【数据范围】
对于 30%的数据，1 ≤ n, m ≤ 10，q = 1；
对于 60%的数据，1 ≤ n, m ≤ 30，q ≤ 10；
对于 100%的数据，1 ≤ n, m ≤ 30，q ≤ 500。
思路框架
第一步，抽离有用状态
第二步，有用状态与有用的后继状态 连边构图， 边权为 由有用状态 到 后继状态 所需的最小步数
第三步，初始状态 到 目标状态 跑最短路
状态的表示
②如何方便的存储状态？
②用0,1,2,3分别表示空白格在指定格的上右下左 状态=（（行号-1）*列数+（列号-1））*4+ 0/1/2/3
int turn(int i,int j) { return (i-1)*m+j-1<<2; }
②状态=turn(x,y)+0/1/2/3
小技巧： 所有网格图中的状态都可以采取类似的方法
状态编号= 图中编号* S+ x ，x∈[0，S)
S=每种编号状态数
一、抽离有用状态
对于1个指定块和一个空白块，有4种有效状态：空白块分别在指定块的上、下、左、右 对于每一种有效状态，有4种后继状态：另外3个方向的状态、交换空白块与指定块 枚举每一个指定块、再枚举指定块的每一个有效状态 bfs计算 到每一个后继状态的最小步数
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]) { if(a[i-1][j]) bfs(i-1,j,i,j,0); if(a[i][j+1]) bfs(i,j+1,i,j,1); if(a[i+1][j]) bfs(i+1,j,i,j,2); if(a[i][j-1]) bfs(i,j-1,i,j,3); }
二、bfs计算边权
前三种后继状态的指定格都位于同一位置
指定格开始在px，py 空白格开始在ex，ey
以ex，ey 为局部初始状态，以另外三个方向的位置为局部目标状态
spfa 计算 空白格移动到 非障碍格 的最小步数当前状态向后继状态连边权为最小步数的边
代码中的pre_dis[][]
前三种状态代码
void bfs(int ex,int ey,int px,int py,int d) { int cx,cy,nx,ny; memset(pre_dis,-1,sizeof(pre_dis)); pre_dis[px][py]=1; pre_dis[ex][ey]=0; cur.x=ex; cur.y=ey; q.push(cur); while(!q.empty()) { cur=q.front(); q.pop(); cx=cur.x,cy=cur.y; for(int i=0; i<4; i++) { nx=cur.x+x[i],ny=cur.y+y[i]; if(a[nx][ny]&&pre_dis[nx][ny]==-1) { pre_dis[nx][ny]=pre_dis[cx][cy]+1; nxt.x=nx; nxt.y=ny; q.push(nxt); } } } if(d==4) return; int tmp=turn(px,py); for(int i=0; i<4; i++) if(pre_dis[px+x[i]][py+y[i]]>0) add(tmp+d,tmp+i,pre_dis[px+x[i]][py+y[i]]); }
特殊的状态
关键看第四种后继状态
他的计算很简单，就是1步
③问题是，问什么会有这一后继状态?
③前面提到 抽离有用状态 造成了状态的不连续
这是不连续的第二层含义
如何理解第四种状态
如果没有第四种状态 我们得到的图大概是这个样子
第四种状态——桥梁
有了第四种状态 大概长这样
也就是说 第四种状态是 将不连续状态连接在一起的桥梁
第四种状态代码
bfs函数最后面加上 add(tmp+d,turn(ex,ey)+(d+2)%4,1);
你现在知道为什么0123分别表示上右下左了吗
状态的有效表示
状态=（（行号-1）*列数+（列号-1））*4+ 0/1/2/3
你现在体会到这种表示方法的强大了吗
三、最短路出解
现在我们有了这样一张图
注意： 终点一定在图内 起点可能与图隔绝
④why？
初始状态与所构图隔绝
④初始状态不一定空白块与指定块挨着 所以初始状态不一定在图中
处理初始状态
如果空白格不与指定格相连， 那么空白格必须先移动到指定格四周
所以可以先让空白格移动到指定格四周
跟第二步同样的方法
将这四个后继状态作为新的初始状态
处理初始状态代码
bfs(ex,ey,sx,sy,4); for(int i=0; i<4; i++) if(pre_dis[sx+x[i]][sy+y[i]]!=-1) { tmp=turn(sx,sy)+i; dis[tmp]=pre_dis[sx+x[i]][sy+y[i]]; k.push(tmp); }
目标状态
思考：目标状态是什么？
最终图示
在本图上跑最短路即可
出结果代码
ans=0x7fffffff; int tmp=turn(tx,ty); for(int i=0; i<4; i++) if(dis[tmp+i]!=-1) ans=min(ans,dis[tmp+i]);
最后的spfa代码
int now; while(!k.empty()) { now=k.front(); k.pop(); v[now]=false; for(int i=front[now]; i; i=nextt[i]) if(dis[to[i]]==-1||dis[to[i]]>dis[now]+w[i]) { dis[to[i]]=dis[now]+w[i]; if(!v[to[i]]) { v[to[i]]=true; k.push(to[i]); } } }
思路梳理
一、有用状态
A、合理高效定义有用状态，并将它不重不漏且方便的体现在代码中
B、找出有用状态并抽离
C、思考它们是否连续
二、构图
A、计算有用状态与其后继状态之间的边权
B、如果有用状态不连续，找到 连接状态之间的桥梁
三、用图论算法出解
A、调整初始状态与目标状态
B、算法出解
上代码：
#include<queue> #include<cstdio> #include<cstring> #include<iostream> using namespace std; const int M = 3601; int n,m,p,num,ans; bool map[32][32],vis[M]; int dx[4]= {-1,0,1,0}, dy[4]= {0,1,0,-1}; int pre_dis[32][32],dis[M],w[M*4],to[M*4],pre[M*4],head[M]; struct Node { int x,y; } cur,nxt; queue<Node>q; queue<int>k; void add(int u,int v,int val) { to[++num]=v; pre[num]=head[u]; head[u]=num; w[num]=val; } int turn(int i,int j) { //（行号-1）*列数+（列号-1） //画一个棋盘，从左上角开始编号，编号从0开始，编一遍 return (i-1)*m+j-1<<2; } void bfs(int ex,int ey,int px,int py,int d) { //指定格开始在px，py; 空白格开始在ex，ey; d是方向 int cx,cy,nx,ny; memset(pre_dis,-1,sizeof(pre_dis)); /* pre_dis数组表示？ 固定指定块，空白块在指定块的一个方向 由这个状态到其他状态的最短路 其他状态：指定块在同一位置，空白块在指定块的另外三个方向 */ pre_dis[px][py]=1;//空白格移动到指定格，两者交换，步数为1 pre_dis[ex][ey]=0;//空白格本就是空白格，不需要移动 cur.x = ex; cur.y = ey; q.push(cur); while(!q.empty()) { cur=q.front(); q.pop(); cx=cur.x, cy=cur.y; for(int i=0; i<4; i++) { nx=cur.x+dx[i],ny=cur.y+dy[i]; if(map[nx][ny] && pre_dis[nx][ny]==-1) { pre_dis[nx][ny]=pre_dis[cx][cy]+1; nxt.x = nx; nxt.y = ny; q.push(nxt); } } } if(d==4) return ; //初始状态连到图里的时候，d=4 //他的结果直接留在pre_dis里作为新的初始状态，不需要连边 int tmp=turn(px,py); for(int i=0; i<4; i++) if(pre_dis[px+dx[i]][py+dy[i]]>0) add(tmp+d,tmp+i,pre_dis[px+dx[i]][py+dy[i]]); //由传入状态向其他方向连边 add(tmp+d,turn(ex,ey)+(d+2)%4,1);//d+2转到相对的方向,转到空白格的对面 } void spfa(int sx,int sy) { int tmp; memset(dis,-1,sizeof(dis));//dis初始值 for(int i=0; i<4; i++) if(pre_dis[sx+dx[i]][sy+dy[i]]!=-1) { tmp=turn(sx,sy)+i; dis[tmp]=pre_dis[sx+dx[i]][sy+dy[i]]; k.push(tmp); } int now; while(!k.empty()) { //k队列中存的初始状态 now=k.front(); k.pop(); vis[now]=false; for(int i=head[now]; i; i=pre[i]) if(dis[to[i]]==-1 || dis[to[i]]>dis[now]+w[i]) { dis[to[i]]=dis[now]+w[i]; if(!vis[to[i]]) { vis[to[i]]=true; k.push(to[i]); } } } } int main() { scanf("%d%d%d",&n,&m,&p); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d",&map[i][j]); for(int i=1; i<=n; i++) //预处理边权 for(int j=1; j<=m; j++) if(map[i][j]) { if(map[i-1][j]) bfs(i-1,j,i,j,0); if(map[i][j+1]) bfs(i,j+1,i,j,1); if(map[i+1][j]) bfs(i+1,j,i,j,2); if(map[i][j-1]) bfs(i,j-1,i,j,3); } for(int i=1; i<=p; i++) { int sx,sy,ex,ey,tx,ty; scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty); if(sx==tx&&sy==ty) { printf("0 "); continue; } bfs(ex,ey,sx,sy,4);//指定格开始在sx，sy; 空白格开始在ex，ey //pre_dis数组在这的作用是初始值 spfa(sx,sy); ans=0x7fffffff; int tmp=turn(tx,ty);//目标状态 for(int i=0; i<4; i++)//在四个目标状态中取最小值 if(dis[tmp+i]!=-1) ans=min(ans,dis[tmp+i]); if(ans==0x7fffffff) ans=-1; printf("%d ",ans); } return 0; }
自己选的路，跪着也要走完！！！