poj3414_bfs

淩亂°似流年 2021-12-08 19:55 314阅读 0赞

题意：这个题以前见过，但是从没有用代码实现过，题意就是，给出两个杯子的容量，求是否可以通过fill,drop,pour,一系列操作，最后得出某一个容量的液体，如果可以则输出最少步数和操作过程，如果不能输出impossible

分析：

这题用bfs,考虑6钟转化过程，这个代码写的有点长。在输出操作过程的时候要递归。

然后就是数据结构的使用了，1A了，感觉不错。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
      2 #include <stdio.h>
      3 #include <cstring>
      4 #include <queue>
      5 using namespace std;
      6 const int maxnum=101;
      7 bool use[maxnum][maxnum];
      8 //196K    0MS  3945B
      9 struct node
     10 {
     11     int x,y;
     12     int ans;
     13     int parent;
     14     int my;
     15     int flag;
     16 }list[maxnum*maxnum];
     17 queue<struct node> q;
     18 
     19 void digui(int u)
     20 {
     21     if(list[u].parent==-1)
     22         return ;
     23     digui(list[u].parent);
     24     if(list[u].flag==11)
     25         printf("FILL(1)\n");
     26     else if(list[u].flag==12)
     27         printf("FILL(2)\n");
     28     else if(list[u].flag==21)
     29         printf("DROP(1)\n");
     30     else if(list[u].flag==22)
     31         printf("DROP(2)\n");
     32     else if(list[u].flag==31)
     33         printf("POUR(1,2)\n");
     34     else if(list[u].flag==32)
     35         printf("POUR(2,1)\n");
     36 }
     37 
     38 int main()
     39 {
     40     int a,b,c,cnt;
     41     scanf("%d%d%d",&a,&b,&c);
     42     memset(use,false,sizeof(use));
     43     use[0][0]=true;
     44     cnt=0;
     45     list[cnt].x=0,list[cnt].y=0,list[cnt].ans=0,list[cnt].parent=-1,list[cnt].my=0;
     46     cnt++;
     47     q.push(list[0]);
     48     struct node temp;
     49     while(!q.empty())
     50     {
     51         temp=q.front();
     52         if(temp.x==c ||temp.y==c)
     53             break;
     54         q.pop();
     55         if(temp.x<a && !use[a][temp.y])
     56         {
     57             use[a][temp.y]=true;
     58             list[cnt].x=a,list[cnt].y=temp.y,list[cnt].ans=temp.ans+1,list[cnt].my=cnt,list[cnt].parent=temp.my,list[cnt].flag=11;
     59             q.push(list[cnt]);
     60             cnt++;
     61         }
     62         if(temp.y<b && !use[temp.x][b])
     63         {
     64             use[temp.x][b]=true;
     65             list[cnt].x=temp.x,list[cnt].y=b,list[cnt].ans=temp.ans+1,list[cnt].my=cnt,list[cnt].parent=temp.my,list[cnt].flag=12;
     66             q.push(list[cnt]);
     67             cnt++;
     68         }
     69         if(temp.x>0 && !use[0][temp.y])
     70         {
     71             use[0][temp.y]=true;
     72             list[cnt].x=0,list[cnt].y=temp.y,list[cnt].ans=temp.ans+1,list[cnt].my=cnt,list[cnt].parent=temp.my,list[cnt].flag=21;
     73             q.push(list[cnt]);
     74             cnt++;
     75         }
     76         if(temp.y>0 &&!use[temp.x][0])
     77         {
     78             use[temp.x][0]=true;
     79             list[cnt].x=temp.x,list[cnt].y=0,list[cnt].ans=temp.ans+1,list[cnt].my=cnt,list[cnt].parent=temp.my,list[cnt].flag=22;
     80             q.push(list[cnt]);
     81             cnt++;
     82         }
     83         if(temp.x>0 && temp.y<b)
     84         {
     85             if(temp.x>=b-temp.y && !use[temp.x-b+temp.y][b])
     86             {
     87                 use[temp.x-b+temp.y][b]=true;
     88                 list[cnt].x=temp.x-b+temp.y,list[cnt].y=b,list[cnt].ans=temp.ans+1,list[cnt].my=cnt,list[cnt].parent=temp.my,list[cnt].flag=31;
     89                 q.push(list[cnt]);
     90                 cnt++;
     91             }
     92             else if(temp.x<b-temp.y && !use[0][temp.y+temp.x])
     93             {
     94                 use[0][temp.y+temp.x]=true;
     95                 list[cnt].x=0,list[cnt].y=temp.y+temp.x,list[cnt].ans=temp.ans+1,list[cnt].my=cnt,list[cnt].parent=temp.my,list[cnt].flag=31;
     96                 q.push(list[cnt]);
     97                 cnt++;
     98             }
     99         }
    100         if(temp.x<a && temp.y>0)
    101         {
    102             if(temp.y>=a-temp.x && !use[a][temp.y-a+temp.x])
    103             {
    104                 use[a][temp.y-a+temp.x]=true;
    105                 list[cnt].x=a,list[cnt].y=temp.y-a+temp.x,list[cnt].ans=temp.ans+1,list[cnt].my=cnt,list[cnt].parent=temp.my,list[cnt].flag=32;
    106                 q.push(list[cnt]);
    107                 cnt++;
    108             }
    109             else if(temp.y<a-temp.x && !use[temp.x+temp.y][0])
    110             {
    111                 use[temp.x+temp.y][0]=true;
    112                 list[cnt].x=temp.x+temp.y,list[cnt].y=0,list[cnt].ans=temp.ans+1,list[cnt].my=cnt,list[cnt].parent=temp.my,list[cnt].flag=32;
    113                 q.push(list[cnt]);
    114                 cnt++;
    115             }
    116         }
    117     }
    118     if(q.empty())
    119         printf("impossible\n");
    120     else
    121     {
    122         printf("%d\n",temp.ans);
    123         digui(temp.my);
    124     }
    125 
    126     return 0;
    127 }
    128 
    129 /*
    130 3 5 4
    131 */

转载于:https://www.cnblogs.com/pushing-my-way/archive/2012/09/26/2703511.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211209/97475005a1fb491ebd67af2f153fb003.png