luogu1979 华容道

luogu1979 华容道

​​ 题目描述

【问题描述】

小 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。

输入输出样例

输入样例#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 说明

【输入输出样例说明】

棋盘上划叉的格子是固定的，红色格子是目标位置，圆圈表示棋子，其中绿色圆圈表示目标棋子。

第一次游戏，空白格子的初始位置是 (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。

首先写一个bfs可以搞到80分

我们可以知道 他的状态只和我白块的位置和我想要动的那块有关，所以我判重直接开四维数组判重即可

我们设定我们要移动的那块为黑块（为了好描述

我每次相当于白块可以随意移动

当我白块移动到黑块旁边时我所要做的就是把黑白两块交换位置，然后继续搜索

知道我的白块在终点了，然后白块的附近就是黑块 那么可以输出答案了

#include#include#include#define inf 0x7f7f7f7f#define N 33using namespace std;int x1[5]={0,0,-1,1};int y1[5]={-1,1,0,0};inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}int map[N][N],n,m,q1,blax,blay,stx,sty,edx,edy;bool visit[N][N][N][N];struct node{ int stx,sty,blax,blay,step; node(){ stx=sty=blax=blay=step=0; }};//visit 前两维是白块的坐标 后两维度是目标块的位置 inline void bfs(){ queue q; node tmp;tmp.stx=stx;tmp.sty=sty;tmp.blax=blax;tmp.blay=blay;q.push(tmp); while (!q.empty()){ tmp=q.front();q.pop(); int stx1=tmp.stx,sty1=tmp.sty,blax1=tmp.blax,blay1=tmp.blay; for (int i=0;i<4;++i){ int nowx=blax1+x1[i],nowy=blay1+y1[i]; if (!map[nowx][nowy]||nowx<1||nowy<1||nowx>n||nowy>m) continue; if (nowx==stx1&&nowy==sty1){ if(visit[nowx][nowy][blax1][blay1]) continue; if (blax1==edx&&blay1==edy) {printf("%d\n",tmp.step+1);return;} else {tmp.blax=nowx,tmp.blay=nowy;tmp.stx=blax1;tmp.sty=blay1;tmp.step++; visit[nowx][nowy][blax1][blay1]=true;q.push(tmp);tmp.step--; } }else{ if (visit[nowx][nowy][stx1][sty1]) continue; tmp.blax=nowx;tmp.blay=nowy;tmp.stx=stx1;tmp.sty=sty1;tmp.step++; visit[nowx][nowy][stx1][sty1]=true;q.push(tmp);tmp.step--; } } } printf("-1\n");}int main(){ freopen("1979.in","r",stdin); n=read();m=read();q1=read(); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) map[i][j]=read(); for (int i=1;i<=q1;++i){ blax=read();blay=read();stx=read();sty=read();edx=read();edy=read(); if (stx==edx&&sty==edy){printf("0\n");continue;} memset(visit,0,sizeof(visit)); visit[blax][blay][stx][sty]=true; bfs(); } return 0;}

我们bfs的瓶颈在于我们的图是固定的，然而我却每次都在非常暴力的去做

满分的做法是提前做一些预处理，然后跑spfa就可以了

我们使用一个三维数组 [x][y][k] 表示白块在(x,y)这个坐标的k号位置（上、下、左、右）

我们每次其实都是需要白块去给铺路才行 那么我就预处理出 白块走到黑块附近需要多少的步数

然后我们还有一种走法可能是我白块在黑块周围了，我需要把白块和黑块进行交换

然后跑spfa 跑spfa的时候 先把我的白块移动到黑块的四周 最后找一下黑块移动到目标节点后 我的白块是在目标节点四周的哪里被枚举到的

本次学习：由于状态只和 白块和黑块的坐标有关所以判重的时候 我们开一个四维数组即可

#include#include#include#define inf 0x7f7f7f7f#define N 33using namespace std;int x1[4]={-1,0,1,0};int y1[4]={0,1,0,-1};inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node1{int x,y,k;};struct node2{node1 y;int next,z;}data[N*N*10];int n,m,q1,h[N][N][N],num;bool flag[N][N],map[N][N];inline int re(int x){return (x+2)%4;}inline void add(int x,int y,int k,node1 t,int z){ data[++num].y=t;data[num].next=h[x][y][k];h[x][y][k]=num;data[num].z=z;}inline int bfs(int xx1,int yy1,int xx2,int yy2){ queue q;memset(flag,0,sizeof(flag)); flag[xx1][yy1]=true;node1 tmp;tmp.x=xx1;tmp.y=yy1;tmp.k=0;q.push(tmp); while (!q.empty()){ node1 xx=q.front();q.pop();int x=xx.x,y=xx.y,z=xx.k; if (x==xx2&&y==yy2) return z; for (int i=0;i<4;++i){ int x2=x+x1[i],y2=y+y1[i]; if (!map[x2][y2]||x2>n||x2<1||y2<1||y2>m) continue; if (!flag[x2][y2]) { tmp.x=x2,tmp.y=y2,tmp.k=z+1;q.push(tmp);flag[x2][y2]=true; } } }return inf;}int f[N][N][4];inline void spfa(int blax,int blay,int stx,int sty,int edx,int edy){ bool flag1[N][N][4];memset(flag1,false,sizeof(flag1));map[stx][sty]=0; queue q;memset(f,0x7f,sizeof(f)); for (int i=0;i<4;++i){ int x=stx+x1[i],y=sty+y1[i]; if (x<1||x>n||y<1||y>m||!map[x][y]) continue; f[stx][sty][i]=bfs(blax,blay,x,y); if (f[stx][sty][i]==inf) continue; node1 tmp;tmp.x=stx,tmp.y=sty;tmp.k=i;q.push(tmp);flag1[stx][sty][i]=true; }map[stx][sty]=1; while (!q.empty()){ node1 tmp;tmp=q.front();q.pop();flag1[tmp.x][tmp.y][tmp.k]=false; for (int i=h[tmp.x][tmp.y][tmp.k];i;i=data[i].next){ node1 to;to=data[i].y;int z=data[i].z; if (f[tmp.x][tmp.y][tmp.k]+zn||x<1||y<1||y>m) continue; node1 tmp;tmp.x=x;tmp.y=y;tmp.k=re(k); add(i,j,k,tmp,1); for (int k1=0;k1<4;++k1){ if (k1<=k) continue; int xx=i+x1[k1],yy=j+y1[k1]; if(!map[xx][yy]||xx>n||xx<1||yy<1||yy>m) continue; int z=bfs(x,y,xx,yy);tmp.x=i;tmp.y=j;tmp.k=k1; add(i,j,k,tmp,z);tmp.x=i;tmp.y=j;tmp.k=k; add(i,j,k1,tmp,z); } }map[i][j]=true; } } //for (int i=1;i<=num;++i) printf("%d %d %d %d\n",data[i].y.x,data[i].y.y,data[i].y.k,data[i].z); for (int i=1;i<=q1;++i){ blax=read();blay=read();stx=read();sty=read();edx=read();edy=read(); if (stx==edx&&sty==edy){printf("0\n");continue;} spfa(blax,blay,stx,sty,edx,edy); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。