看别人的代码然后被坑了一下午+一晚上,睡一觉第二天醒悟过来打表过了

果然打表才是正确的调试方法,跟踪什么的去屎(╯‵□′)╯︵┻━┻

原题:

小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程来完成华容道:给定一种局面,华容道是否根本就无法完成,如果能完成,最少需要多少时间。
小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的:
1.     在一个 n*m 棋盘上有 n*m 个格子,其中有且只有一个格子是空白的,其余 n*m-1 个格子上每个格子上有一个棋子,每个棋子的大小都是 1*1 的;
2.     有些棋子是固定的,有些棋子则是可以移动的;
3.     任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。
游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。
    
给定一个棋盘,游戏可以玩 q 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次玩的时候,空白的格子在第 EX[i] 行第 EY[i] 列,指定的可移动棋子的初始位置为第 SX[i] 行第 SY[i] 列,目标位置为第 TX[i] 行第 TY[i] 列。
假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请
你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。

1 ≤ n, m ≤ 30,q ≤ 500。

这题暴力分很实惠,很容易写出一个bfs能拿到60-70

想要A掉怎么办呐

正解就要魔性p♂l♀a♂y了

用一个状态b[i][j][k][h]表示第i行第j列的格子,空格在k方向,这个格子要移动到h方向需要的最小步数

这个步数怎么求呐

可以用一个bfs,求出空格从k方向到h方向需要的步数,然后需要移动的格子和h方向的空格交换即可,可以证明这样做是最优的(逃

然后一个三维的点c[i][j][k]表示第i行第j列的格子,空格在k方向,上面用bfs求出步数↑后就可以把c[i][j][k]与c[i+k方向上x的变化量][j+k方向上y的变化量][h的反方向]连上权值为步数的边

因为求出步数的方法是先把空格移到h方向,在把格子和空格交换↑,所以边的汇点的方向是h的反方向

然后每次询问的时候,可以直接套用上面的bfs↑求出把空白格移动到要移动的方格附近需要的步数,四个方向都搞一下,建一个源点s,把s与c[i][j][k]连上权值为步数的边

然后再建一个汇点t,把t和c[目标节点x][目标节点y][四个方向]连上权值为0的边

然后就可以开心地搞最短路辣

需要注意的的方:

最好判断一下要移动的格子和目标格子是一个东西以及要移动的格子或目标格子不合法的情况

连边的时候需要注意什么时候坐标要加上方向,什么时候坐标是原格子

小技巧:
可以用一个计数,在输入数据的时候给每个c[i][j][k]都标上号,连边的时候就很方便

把x和y的变化量分别设成{1,-1,0,0},{0,0,1,-1},这样直接用k^1就可以快速取到反向边

代码:

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int oo=;
int fx[]={,-,,},fy[]={,,,-};
struct ddd{int next,y,value;}e[];int LINK[],ltop=;
inline void insert(int x,int y,int z){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;e[ltop].value=z;}
int m,n,q,a[][];
int hash[][][],hash_cnt=;
int dui[],tou=;
int bf[][];
int s,t;
int sf[];
bool visited[];
int bfs(int sx,int sy,int tx,int ty){
memset(bf,,sizeof(bf));
dui[tou=]=(sx-)*n+sy-; bf[sx][sy]=;
for(int k=;k<=tou;k++){
int x=dui[k]/n+,y=dui[k]%n+;
for(int i=;i<;i++)if(a[x+fx[i]][y+fy[i]] && bf[x+fx[i]][y+fy[i]]>bf[x][y]+){
bf[x+fx[i]][y+fy[i]]=bf[x][y]+;
//if(x+fx[i]==tx && y+fy[i]==ty) return bf[tx][ty];
dui[++tou]=(x+fx[i]-)*n+y+fy[i]-;
}
}
return bf[tx][ty];
}
int spfa(){
memset(sf,,sizeof(sf));
memset(visited,,sizeof(visited));
dui[tou=]=s; sf[s]=;
for(int k=;k<=tou;k++){
visited[dui[k]]=false;
for(int i=LINK[dui[k]];i;i=e[i].next)
if(sf[e[i].y]>sf[dui[k]]+e[i].value){
sf[e[i].y]=sf[dui[k]]+e[i].value;
if(!visited[e[i].y]) dui[++tou]=e[i].y,visited[e[i].y]=true;
}
}
return (sf[t]<oo) ? sf[t] : -;
}
int main(){//freopen("ddd.in","r",stdin);
cin>>m>>n>>q;
for(int i=;i<=m;i++) for(int j=;j<=n;j++){
scanf("%d",&a[i][j]);
for(int k=;k<;k++) hash[i][j][k]=++hash_cnt;
}
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)if(a[i][j])
for(int k=;k<;k++)if(a[i+fx[k]][j+fy[k]]){
insert(hash[i][j][k],hash[i+fx[k]][j+fy[k]][k^],);
//cout<<i<<" "<<j<<" "<<k<<" "<<i+fx[k]<<" "<<j+fy[k]<<" "<<(k^1)<<" "<<1<<endl;
for(int q=;q<;q++)if(q!=k && a[i+fx[q]][j+fy[q]]){
a[i][j]=;
int bu=bfs(i+fx[k],j+fy[k],i+fx[q],j+fy[q])+;
if(bu<oo){ insert(hash[i][j][k],hash[i+fx[q]][j+fy[q]][q^],bu); /*cout<<i<<" "<<j<<" "<<k<<" "<<i+fx[q]<<" "<<j+fy[q]<<" "<<(q^1)<<" "<<bu<<endl;*/}
a[i][j]=;
}
}
int sx,sy,tx,ty,kx,ky;
while(q --> ){//趋向于
scanf("%d%d%d%d%d%d",&kx,&ky,&sx,&sy,&tx,&ty);
if(sx==tx && sy==ty){ printf("0\n"); continue;}
if(!a[sx][sy] || !a[tx][ty]){ printf("-1\n"); continue;}
s=++hash_cnt;t=++hash_cnt;
a[sx][sy]=;
for(int k=;k<;k++)if(a[sx+fx[k]][sy+fy[k]]){
int bu=bfs(kx,ky,sx+fx[k],sy+fy[k]);
if(bu<oo) insert(s,hash[sx][sy][k],bu);
}
a[sx][sy]=;
for(int k=;k<;k++)if(a[tx+fx[k]][ty+fy[k]])
insert(hash[tx][ty][k],t,);
printf("%d ",spfa());
}
return ;
}

最新文章

  1. ASP.NET MVC中使用Unity Ioc Container
  2. spark API 介绍链接
  3. Android 屏幕适配
  4. DedeCms文档关键词替换,优先替换长尾关键词
  5. strust.xml
  6. 加密算法使用(二):使用MD5加密字符串(另:byte数组转16进制自动补零方法写法)
  7. Hadoop伪分布式模式部署
  8. Android Fragment 真正彻底的解决(下一个)
  9. 从头编写 asp.net core 2.0 web api 基础框架 (1)
  10. mac通过自带的ssh连接Linux服务器并上传解压文件
  11. QQ登录的那些坑
  12. React Native不同设备分辨率适配和设计稿尺寸单位px的适配
  13. C#多线程编程のSemaphore(信号量,负责协调各个线程)
  14. 【转】java String.split()函数的用法分析
  15. css BFC布局及用处
  16. Revit MEP API连接器类别
  17. 【Unity】11.3 基本碰撞体(箱体、球形、胶囊、网格)
  18. windows下的IO模型之完成端口
  19. 8.使用Exists监控ZNode的三大Change事件
  20. php-streams扩展学习

热门文章

  1. OpenCV坐标体系的初步认识
  2. 弹框工作区(dialog)
  3. javascript中创建对象的几种方式
  4. C++ primer的第二章的主要内容
  5. zoj1530 bfs
  6. javaweb-c3p0
  7. @font-face usage
  8. 关于EOF和循环体的搭配使用。
  9. BZOJ 1853 幸运数字
  10. PHP中的数组(二)常用数组处理函数