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。
思路:
考虑一下怎么做这题:
①灵活改变状态表示方法，整合无用状态，减少无用状态
②将状态抽离，构图，转化为图论问题
故:正确的步骤为
第一步，抽离有用状态
第二步，有用状态与有用的后继状态 连边构图，
边权为：由有用状态 到 后继状态 所需的最小步数
第三步，初始状态 到 目标状态 ，跑最短路（最好是跑spfa）
所以正解就出来啦~~即bfs+spfa
技巧:
我们可以用0,1,2,3分别表示空白格在指定格的上右下左
状态=（（行号-1）*列数+（列号-1））*4+ 0/1/2/3
int numbers(int i,int j) { return (i-1)*m+j-1<<2; } 状态=number(x,y)+0/1/2/3
其实所有网格图中的状态都可以采取类似的方法
状态编号= 图中编号* S+ x ，x∈[0，S) S=每种编号状态数
所以在定义dx数组跟dy数组的时候一定要一一对应!!!
坑点:
①如上技巧所述：
在定义dx数组跟dy数组的时候一定要一一对应!!!不然很吃亏...
②写n,m千万不要写反了...写反了很尴尬,读不进去...虽然是可以检查出来,不过这个真的很致命!!!!
③在进行连边的时候，其实还有第四种后继状态：
就是空白格与指定格的位置互换
我使用的是上右下左这样的dx，dy，所以第四种状态的转换就简单的变为{空白格的numbers+（d+2）%4} ps：d是枚举的初始状态空白格相对于指定格的方向。
除此之外的状态用指定格的numbers+d即可
代码:
因为我细心的敲了好多注释，快夸我快夸我=w=
#include <iostream> #include <cstring> #include <cstdio> #include <queue> #define INF 0x7fffffff using namespace std; const int Maxt = 32; const int Maxn = 3610; const int Maxm = Maxn * 5; int n,m,p; bool a[Maxt][Maxt],vis[Maxn]; int dx[4] = {-1,0,1, 0}, dy[4] = { 0,1,0,-1}; int predis[Maxt][Maxt],dis[Maxn]; struct game { int next,to,w; }e[Maxm]; int top,head[Maxn]; void add(int u,int v,int val) { top++; e[top].to=v; e[top].w=val; e[top].next=head[u]; head[u]=top; } struct start { int x,y; } nxt,cur; queue<start>q; queue<int>que; int numbers(int i,int j) { /* 因为固定一个指定块之后的状态对应着5种状态, 都是不同的状态,所以要开5倍,即必须编号多编 */ j--; ///从0开始编号 return (i-1)*m+j<<2; // return (i-1)*m+j<<2; ///如果像这样从1开始编号的话,我们的存图的struct game e数组就需要多开5个空间!!!所以还是最好从0编号好 } void bfs(int ex,int ey,int px,int py,int d) { int cx,cy,nx,ny; memset(predis,-1,sizeof(predis)); /* predis数组表示啥呢??? 其实简单来说就是: 固定指定块,空白块在指定块的其中一个方向 然后再由这个状态到其他状态的最短路 没错!储存的就是最短路的距离!!! 其他状态是指: 固定了指定块之后,空白块在指定块的另外三个方向 */ ///指定格 predis[px][py]=1; ///空白格 predis[ex][ey]=0; ///bfs当前空白格移动到每个点所需要的步数 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(a[nx][ny] && predis[nx][ny]==-1) { predis[nx][ny]=predis[cx][cy]+1; nxt.x=nx,nxt.y=ny; q.push(nxt); } } } ///如刚才所述 if(d==8) return; int tmp=numbers(px,py); for(int i=0; i<4; ++i) { int x=px+dx[i],y=py+dy[i]; if(predis[x][y]>0) /* 因为在之前已经把predis[ex][ey]赋值为0, 所以这个条件就是相当于当前枚举的这个指定块与空白块的状态, 与它的后继状态进行连边 */ /*----------这里重要----------*/ add(tmp+d,tmp+i,predis[x][y]); /*----------真的重要----------*/ } /* 最后一种后继状态是指定格与空白格交换位置 因为规定的0123是上右下左,所以(d+2)%4可以直接转化为对面的方向 交换相当于走一步,所以边权为1 */ add(tmp+d,numbers(ex,ey)+(d+2)%4,1); } void spfa(int sx,int sy) { int tmp; memset(dis,-1,sizeof(dis)); for(int i=0; i<4; ++i) { int x=sx+dx[i],y=sy+dy[i]; if(predis[x][y]!=-1) { tmp=numbers(sx,sy)+i; dis[tmp]=predis[x][y]; que.push(tmp); } } int u; while(!que.empty()) { u=que.front(); que.pop(); vis[u]=false; for(int i=head[u]; i; i=e[i].next) { int v=e[i].to; if(dis[v]==-1 || dis[v]>dis[u]+e[i].w) { dis[v]=dis[u]+e[i].w; if(!vis[v]) { vis[v]=true; que.push(v); } } } } } 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",&a[i][j]); for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) if(a[i][j]) { ///枚举固定空白格,上,右,下,左(顺时针旋转,方便进行转换) ///bfs在固定指定格与空白格的5种状态 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); } /* 空白格：ex,ey 指定格的初始位置：sx,sy 目标位置：tx,ty */ int ex,ey,sx,sy,tx,ty,ans; while(p--) { scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty); if(sx==tx && sy==ty) { printf("0 "); continue; } /*-----------最后一次bfs-----------*/ /* 因为我们是直接枚举空白快与指定块连接在一起的状态, 但是他们其实有可能初始状态并没有连接, 所以强行将她们进行连接, 但是不在图中进行连边, 所以随便弄个d,如果bfs之后要建边了, 若是胡乱搞的这个d,直接return即可 */ bfs(ex,ey,sx,sy,8); ///普♂通♀的spfa,跑最短路 spfa(sx,sy); ans=INF; ///将目标位置进行编号 int tmp=numbers(tx,ty); for(int i=0; i<4; ++i) ///+i是空白块的状态方向 if(dis[tmp+i]!=-1) ///往小里面更新 ans=min(ans,dis[tmp+i]); if(ans==INF) ans=-1; printf("%d ",ans); } return 0; }