devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

学习总结2

作者：知新_RL | 2024-03-23 08:22:03

赞

踩

学习总结2

解题思路

用bfs进行搜索,标记A罐B罐所保存的水的出现情况,当再次出现的时候停止搜索,然后用数组模拟链表进行保存路径.最后输出.

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <fstream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <deque>
  7. #include <vector>
  8. #include <queue>
  9. #include <string>
  10. #include <cstring>
  11. #include <map>
  12. #include <stack>
  13. #include <set>
  14. using namespace std;
  15. int g[120][120];
  16. struct s
  17. {
  18.     int x;
  19.     int y;
  20. }d[120*120];
  21. int l,r;
  22. struct ss
  23. {
  24.     int x;
  25.     int y;
  26.     int z;
  27. }j[120][120];
  28. int a,b,c;
  29. int k,i;
  30. int bfs()
  31. {
  32.     int tx,ty,z;
  33.     while(l<r)
  34.     {
  35.         for(z=0;z<6;z++)
  36.         {
  37.             tx=d[l].x;
  38.             ty=d[l].y;
  39.             switch(z)
  40.             {
  41.                 case 0:tx=a;break;
  42.                 case 1:ty=b;break;
  43.                 case 2:tx=0;break;
  44.                 case 3:ty=0;break;
  45.                 case 4:
  46.                     if(tx!=0)
  47.                     {
  48.                         if(tx+ty<=b)
  49.                         {
  50.                             ty=tx+ty;
  51.                             tx=0;
  52.                         }
  53.                         else
  54.                         {
  55.                             tx=tx-(b-ty);
  56.                             ty=b;
  57.                         }
  58.                     }
  59.                     break;
  60.                 case 5:
  61.                     if(ty!=0)
  62.                     {
  63.                         if(tx+ty<=a)
  64.                         {
  65.                             tx=ty+tx;
  66.                             ty=0;
  67.                         }
  68.                         else
  69.                         {
  70.                             ty=ty-(a-tx);
  71.                             tx=a;
  72.                         }
  73.                     }
  74.                     break;
  75.             }
  76.             if(tx>a||ty>b||tx<0||ty<0)
  77.                 continue;
  78.             if(tx==c||ty==c)
  79.             {
  80.                 k=tx;
  81.                 i=ty;
  82.                 j[k][i].x=d[l].x;
  83.                 j[k][i].y=d[l].y;
  84.                 j[k][i].z=z;
  85.                 g[tx][ty]=g[d[l].x][d[l].y]+1;
  86.                 return 0;
  87.             }
  88.             if(g[tx][ty]==-1)
  89.             {
  90.                 g[tx][ty]=g[d[l].x][d[l].y]+1;
  91.                 d[r].x=tx;
  92.                 d[r++].y=ty;
  93.                 j[tx][ty].x=d[l].x;
  94.                 j[tx][ty].y=d[l].y;
  95.                 j[tx][ty].z=z;
  96.             }
  97.         }
  98.         l++;
  99.     }
  100.     return 0;
  101. }
  102.  
  103. void print(int x,int y)
  104. {
  105.     if(x==0&&y==0)
  106.         return ;
  107.     print(j[x][y].x,j[x][y].y);
  108.     switch(j[x][y].z)
  109.     {
  110.         case 0:printf("FILL(1)\n");break;
  111.         case 1:printf("FILL(2)\n");break;
  112.         case 2:printf("DROP(1)\n");break;
  113.         case 3:printf("DROP(2)\n");break;
  114.         case 4:printf("POUR(1,2)\n");break;
  115.         case 5:printf("POUR(2,1)\n");break;
  116.     }
  117.     return ;
  118. }
  119.  
  120. int main()
  121. {
  122.     scanf("%d%d%d",&a,&b,&c);
  123.     d[r].x=0;
  124.     d[r++].y=0;
  125.     memset(g,-1,sizeof(int )*120*120);
  126.     g[0][0]=0;
  127.     bfs();
  128.     if(k==0&&i==0)
  129.     {
  130.         printf("impossible\n");
  131.     }
  132.     else
  133.     {
  134.         printf("%d\n",g[k][i]);
  135.         print(k,i);
  136.     }
  137.     return 0;
  138. }

解题思路

这道题用bfs就行了.以两个人为起点对全图进行搜索,用一个数组保存到每一个地方所用的最短的步数.最后比较两人到所有的kfc所用的步数的总和输出最小的就行了.

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <fstream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <deque>
  7. #include <vector>
  8. #include <queue>
  9. #include <string>
  10. #include <cstring>
  11. #include <map>
  12. #include <stack>
  13. #include <set>
  14. using namespace std;
  15. char g[210][210];
  16. int j[210][210];
  17. int j2[210][210];
  18. int ne[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
  19. int n,m;
  20. struct di
  21. {
  22.     int x;
  23.     int y;
  24. }sy,sm,kfc[210*210],dl[210*210];
  25. int l,r;
  26. int k;
  27. int sum;
  28.  
  29.  
  30. int bfs()
  31. {
  32.     int tx,ty,z;
  33.     while(l<r)
  34.     {
  35.         for(z=0;z<4;z++)
  36.         {
  37.             tx=ne[z][0]+dl[l].x;
  38.             ty=ne[z][1]+dl[l].y;
  39.             if(tx<0||tx>n||ty<0||ty>m)
  40.                 continue;
  41.             if(g[tx][ty]!='#'&&j[tx][ty]==0)
  42.             {
  43.                 j[tx][ty]=j[dl[l].x][dl[l].y]+1;
  44.                 dl[r].x=tx;
  45.                 dl[r++].y=ty;
  46.             }
  47.         }
  48.         l++;
  49.     }
  50.     return 0;
  51. }
  52.  
  53. int bfs2()
  54. {
  55.     int tx,ty,z;
  56.     while(l<r)
  57.     {
  58.         for(z=0;z<4;z++)
  59.         {
  60.             tx=ne[z][0]+dl[l].x;
  61.             ty=ne[z][1]+dl[l].y;
  62.             if(tx<0||tx>n||ty<0||ty>m)
  63.                 continue;
  64.             if(g[tx][ty]!='#'&&j2[tx][ty]==0)
  65.             {
  66.                 j2[tx][ty]=j2[dl[l].x][dl[l].y]+1;
  67.                 dl[r].x=tx;
  68.                 dl[r++].y=ty;
  69.             }
  70.         }
  71.         l++;
  72.     }
  73.     return 0;
  74. }
  75.  
  76. int main()
  77. {
  78.     int x,y,s;
  79.     while(~scanf("%d%d",&n,&m))
  80.     {
  81.         sum=9999999;
  82.         k=0;
  83.         for(x=0;x<n;x++)
  84.         {
  85.             scanf("%s",g[x]);
  86.         }
  87.         for(x=0;x<n;x++)
  88.         {
  89.             for(y=0;y<m;y++)
  90.             {
  91.                 if(g[x][y]=='Y')
  92.                 {
  93.                     sy.x=x;
  94.                     sy.y=y;
  95.                 }
  96.                 if(g[x][y]=='M')
  97.                 {
  98.                     sm.x=x;
  99.                     sm.y=y;
  100.                 }
  101.                 if(g[x][y]=='@')
  102.                 {
  103.                     kfc[k].x=x;
  104.                     kfc[k++].y=y;
  105.                 }
  106.             }
  107.         }
  108.  
  109.         memset(j,0,sizeof(int)*210*210);
  110.         l=0;
  111.         r=0;
  112.         dl[r].x=sy.x;
  113.         dl[r++].y=sy.y;
  114.         bfs();
  115.  
  116.         memset(j2,0,sizeof(int)*210*210);
  117.         l=0;
  118.         r=0;
  119.         dl[r].x=sm.x;
  120.         dl[r++].y=sm.y;
  121.         bfs2();
  122.  
  123.         for(x=0;x<k;x++)
  124.         {
  125.             if(j[kfc[x].x][kfc[x].y]!=0&&j2[kfc[x].x][kfc[x].y]!=0)
  126.             if((j[kfc[x].x][kfc[x].y]+j2[kfc[x].x][kfc[x].y])<sum)
  127.                 sum=j[kfc[x].x][kfc[x].y]+j2[kfc[x].x][kfc[x].y];
  128.         }
  129.         printf("%d\n",sum*11);
  130.     }
  131.     return 0;
  132. }

解题思路

用bfs搜索,要注意的是地图是三维的,传送到下一层之后可能的情况(直接见到公主,撞死,进入另一个传送门).

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <fstream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <deque>
  7. #include <vector>
  8. #include <queue>
  9. #include <string>
  10. #include <cstring>
  11. #include <map>
  12. #include <stack>
  13. #include <set>
  14. using namespace std;
  15. char g[3][15][15];
  16. int j[3][15][15];
  17. struct ss
  18. {
  19.     int x;
  20.     int y;
  21.     int z;
  22. }d[15*15*3];
  23. int ne[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
  24. int l,r;
  25. int n,m,t;
  26. int bfs()
  27. {
  28.     int z,tx,ty,tz;
  29.     while(l<r)
  30.     {
  31.         for(int z=0;z<4;z++)
  32.         {
  33.             tx=d[l].x+ne[z][0];
  34.             ty=d[l].y+ne[z][1];
  35.             tz=d[l].z;
  36.             if(tx<0||ty<0||tx>=n||ty>=m)
  37.                 continue;
  38.             if(g[tz][tx][ty]=='P')
  39.             {
  40.                 return j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;
  41.             }
  42.             if(g[tz][tx][ty]!='*'&&j[tz][tx][ty]==-1)
  43.             {
  44.                 j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;
  45.                 if(g[tz][tx][ty]=='#')
  46.                 {
  47.                     if(tz==0)
  48.                     {
  49.                         tz++;
  50.                     }
  51.                     else
  52.                     {
  53.                         tz--;
  54.                     }
  55.                     if(g[tz][tx][ty]=='#'||j[tz][tx][ty]!=-1)
  56.                     {
  57.                         if(tz==0)
  58.                         {
  59.                             tz++;
  60.                         }
  61.                         else
  62.                         {
  63.                             tz--;
  64.                         }
  65.                         continue;
  66.                     }
  67.                     if(g[tz][tx][ty]=='*'||j[tz][tx][ty]!=-1)
  68.                     {
  69.                         if(tz==0)
  70.                         {
  71.                             tz++;
  72.                         }
  73.                         else
  74.                         {
  75.                             tz--;
  76.                         }
  77.                         continue;
  78.                     }
  79.                     if(g[tz][tx][ty]=='P')
  80.                     {
  81.                         return j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;
  82.                     }
  83.                     j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;
  84.                 }
  85.                 d[r].x=tx;
  86.                 d[r].y=ty;
  87.                 d[r++].z=tz;
  88.             }
  89.         }
  90.         l++;
  91.     }
  92.     return 999999;
  93. }
  94. int main()
  95. {
  96.     int k;
  97.     scanf("%d",&k);
  98.     for(int z=0;z<k;z++)
  99.     {
  100.         memset(j,-1,sizeof(int )*3*15*15);
  101.         l=r=0;
  102.         scanf("%d%d%d",&n,&m,&t);
  103.         for(int x=0;x<n;x++)
  104.         {
  105.             scanf("%s",g[0][x]);
  106.         }
  107.         getchar();
  108.         for(int x=0;x<n;x++)
  109.         {
  110.             scanf("%s",g[1][x]);
  111.         }
  112.  
  113.         d[r].x=0;
  114.         d[r].y=0;
  115.         d[r++].z=0;
  116.         j[0][0][0]=0;
  117.         int sum=bfs();
  118.         if(sum<=t)
  119.         {
  120.             printf("YES\n");
  121.         }
  122.         else
  123.         {
  124.             printf("NO\n");
  125.         }
  126.     }
  127.     return 0;
  128. }

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号