首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐
2025年7月23日 星期三 2:25am

poj2049 - Finding Nemo

  • 24-03-05 06:41
  • 2168
  • 12790
blog.csdn.net

                                  想看更多的解题报告: http://iyenn.com/rec/1824570.html
                                  转载请注明出处:http://blog.csdn.net/wangjian8006

题目大意:有一个迷宫,在迷宫中有墙与门
有m道墙,每一道墙表示为(x,y,d,t)
x,y表示墙的起始坐标
d为0即向右t个单位,都是墙
d为1即向上t个单位,都是墙
有n道门,每一道门表示为(x,y,d)
x,y表示门的起始坐标
d为0即向右一个单位表示门
d为1即向上一个单位表示门
再给出你起点的位置(f1,f2),并保证这个点的位置不会再墙或者门中,为起点到(0,0)最少要穿过多少条门

注意:在迷宫中不只有门和墙,还有空地,因为理解错题目意思WA了一上午。

 

 


解题思路:调试的我有点头晕.
将坐标系看成网格,在这里我以每个格子的左下点为基点,那么坐标对应网格
坐标(0,0)的网格为(1,1)
坐标(1,1)的网格为(2,2)
坐标(1,2)的网格为(2,3)
...
依次类推

我再定义xa[i][j]代表网格(i,j)的上边的值
ya[i][j]代表网格(i,j)的右边的值
值分为三种,空地,墙,门
空地为0,墙为INF,门为1
首先全赋值为空地
然后根据输入来赋值
这样就便于搜索了
这里要注意的是要全部搜索完,因为要穿过最少的门,用优先队列搞定
还有当在迷宫外面时,直接输出0,这个不看讨论版真会WA到死
因为迷宫可能在[1,199]但是目标人物所在坐标可能超出这个范围

 

  1. /*
  2. Memory 708K
  3. Time 32MS
  4. */
  5. #include
  6. #include
  7. using namespace std;
  8. #define MAXV 210
  9. #define INF 1<<29
  10. #define min(a,b) (a>b?b:a)
  11. #define max(a,b) (a>b?a:b)
  12. #define EMPTY 0
  13. #define DOOR 1
  14. #define WALL INF
  15. int xa[MAXV][MAXV],ya[MAXV][MAXV];
  16. int dis[MAXV][MAXV];
  17. int dt[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
  18. int xmax,ymax;
  19. bool pd(int x,int y){
  20. if(x>0 && x<=xmax && y<=ymax && y>0) return 1;
  21. return 0;
  22. }
  23. int getvalue(int x,int y,int i){
  24. if(i==0) return ya[x-1][y];
  25. if(i==1) return ya[x][y];
  26. if(i==2) return xa[x][y-1];
  27. return xa[x][y];
  28. }
  29. int bfs(int tx,int ty){
  30. int i,j,vx,vy,dx,dy,tmp;
  31. queue <int>q;
  32. for(i=1;i<=ymax;i++){
  33. for(j=1;j<=xmax;j++)
  34. dis[i][j]=INF;
  35. }
  36. dis[1][1]=0;
  37. q.push(1);
  38. q.push(1);
  39. while(!q.empty()){
  40. vx=q.front();q.pop();
  41. vy=q.front();q.pop();
  42. for(i=0;i<4;i++){
  43. dx=vx+dt[i][0];
  44. dy=vy+dt[i][1];
  45. tmp=getvalue(vx,vy,i);
  46. if(pd(dx,dy) && dis[dx][dy]>dis[vx][vy]+tmp){
  47. dis[dx][dy]=dis[vx][vy]+tmp;
  48. q.push(dx);
  49. q.push(dy);
  50. }
  51. }
  52. }
  53. return (dis[tx][ty]==INF?-1:dis[tx][ty]);
  54. }
  55. int main(){
  56. int n,m,i,j;
  57. int x,y,d,t;
  58. double sx,sy;
  59. while(scanf("%d%d",&m,&n)){
  60. if(m==-1 && n==-1) break;
  61. ymax=xmax=-1;
  62. memset(xa,EMPTY,sizeof(xa));
  63. memset(ya,EMPTY,sizeof(ya));
  64. for(i=0;i
  65. scanf("%d%d%d%d",&x,&y,&d,&t);
  66. if(d){
  67. for(j=0;j1]=WALL;
  68. ymax=max(y+t+1,ymax);
  69. xmax=max(x+1,xmax);
  70. }else{
  71. for(j=0;j1][y]=WALL;
  72. ymax=max(y+1,ymax);
  73. xmax=max(x+t+1,xmax);
  74. }
  75. }
  76. for(i=0;i
  77. scanf("%d%d%d",&x,&y,&d);
  78. if(d) ya[x][y+1]=DOOR;
  79. else xa[x+1][y]=DOOR;
  80. }
  81. scanf("%lf%lf",&sx,&sy);
  82. if(!(sx>=1 && sx<=199 && sy>=1 && sy<=199)) printf("0\n");
  83. else printf("%d\n",bfs((int)sx+1,(int)sy+1));
  84. }
  85. return 0;
  86. }


 

注:本文转载自blog.csdn.net的wangjian8006的文章"http://blog.csdn.net/wangjian8006/article/details/7997609"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top