欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ-3414 Pots(两个杯子倒水问题) 【BFS】

程序员文章站 2022-05-20 20:24:36
...

题目传送门

题目:

给你两个杯子,分别是A和B升。可以执行以下操作:

1.FILL(i):将i倒满水。
2.DROP(i):将i倒空水。
3.POUR(i,j): 将ipot的水倒到jpot上,直至要么ipot为空,要么jpot为满。

求能否在一定步数的操作后,使得a,b某一个杯子中的水为c,输出最少的操作数和操作步骤,若不能,输出impossible.

题解:

用BFS搜索最短路径步数,同时记录最短路径。(代码很长,但是足够耐心是一定可以看懂的(`・ω・´)。)

AC代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define io ios::sync_with_stdio(0),cin.tie(0)
#define ms(arr) memset(arr,0,sizeof(arr))
#define inf 0x3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e5+7;
struct P
{
    int x,y;
    int sx,sy;
    int v;//倒水操作
    int vis;
    int num;
}cup[110][110];
int a,b,c;
int flag;
int xx,yy,xxx,yyy;
int path[maxn];
void bfs()
{
    queue <P> q;
    q.push(cup[0][0]);
    cup[0][0].vis=1;
    while(!q.empty())
    {
        P p=q.front();
        q.pop();
        xx=p.x;
        yy=p.y;
        if(xx==c||yy==c)
        {
            flag=1;
            break;
        }
        if(p.x>=0&&p.x<=a&&p.y>=0&&p.y<=b)
        {
            if(cup[a][p.y].vis==0)//杯子a加满
            {
                cup[a][p.y].sx=p.x;
                cup[a][p.y].sy=p.y;
                cup[a][p.y].vis=1;
                cup[a][p.y].num=p.num+1;
                cup[a][p.y].v=1;
                q.push(cup[a][p.y]);
            }
            if(cup[0][p.y].vis==0)//杯子a倒空
            {
                cup[0][p.y].sx=p.x;
                cup[0][p.y].sy=p.y;
                cup[0][p.y].vis=1;
                cup[0][p.y].num=p.num+1;
                cup[0][p.y].v=2;
                q.push(cup[0][p.y]);
            }
            if(cup[p.x][b].vis==0)//杯子b加满
            {
                cup[p.x][b].sx=p.x;
                cup[p.x][b].sy=p.y;
                cup[p.x][b].vis=1;
                cup[p.x][b].num=p.num+1;
                cup[p.x][b].v=3;
                q.push(cup[p.x][b]);
            }
            if(cup[p.x][0].vis==0)//杯子b倒空
            {
                cup[p.x][0].sx=p.x;
                cup[p.x][0].sy=p.y;
                cup[p.x][0].vis=1;
                cup[p.x][0].num=p.num+1;
                cup[p.x][0].v=4;
                q.push(cup[p.x][0]);
            }
            if(p.x-(b-p.y)>0&&cup[p.x-(b-p.y)][b].vis==0)//a倒入b,a有剩余
            {
                cup[p.x-(b-p.y)][b].sx=p.x;
                cup[p.x-(b-p.y)][b].sy=p.y;
                cup[p.x-(b-p.y)][b].vis=1;
                cup[p.x-(b-p.y)][b].num=p.num+1;
                cup[p.x-(b-p.y)][b].v=5;
                q.push(cup[p.x-(b-p.y)][b]);
            }
            if(p.x-(b-p.y)<=0&&cup[0][p.x+p.y].vis==0)//a倒入b,a空
            {
                cup[0][p.x+p.y].sx=p.x;
                cup[0][p.x+p.y].sy=p.y;
                cup[0][p.x+p.y].vis=1;
                cup[0][p.x+p.y].num=p.num+1;
                cup[0][p.x+p.y].v=5;
                q.push(cup[0][p.x+p.y]);
            }
            if(p.y-(a-p.x)>0&&cup[a][p.y-(a-p.x)].vis==0)//b倒入a,b有剩余
            {
                cup[a][p.y-(a-p.x)].sx=p.x;
                cup[a][p.y-(a-p.x)].sy=p.y;
                cup[a][p.y-(a-p.x)].vis=1;
                cup[a][p.y-(a-p.x)].num=p.num+1;
                cup[a][p.y-(a-p.x)].v=6;
                q.push(cup[a][p.y-(a-p.x)]);
            }
            if(p.y-(a-p.x)<=0&&cup[p.x+p.y][0].vis==0)//b倒入a,b空
            {
                cup[p.x+p.y][0].sx=p.x;
                cup[p.x+p.y][0].sy=p.y;
                cup[p.x+p.y][0].vis=1;
                cup[p.x+p.y][0].num=p.num+1;
                cup[p.x+p.y][0].v=6;
                q.push(cup[p.x+p.y][0]);
            }
        }
    }
    if(flag==1)
    {
        printf("%d\n",cup[xx][yy].num);
        int sum=cup[xx][yy].num;
        for(int i=sum;i>0;i--)
        {
            path[i]=cup[xx][yy].v;
            xxx=xx;
            yyy=yy;
            xx=cup[xxx][yyy].sx;
            yy=cup[xxx][yyy].sy;
        }
        for(int i=1;i<=sum;i++)
        {
            if(path[i]==1) printf("FILL(1)\n");
            else if(path[i]==2) printf("DROP(1)\n");
            else if(path[i]==3) printf("FILL(2)\n");
            else if(path[i]==4) printf("DROP(2)\n");
            else if(path[i]==5) printf("POUR(1,2)\n");
            else if(path[i]==6) printf("POUR(2,1)\n");
        }
    }
    else
        printf("impossible\n");
    return ;
}
int main()
{
    scanf("%d%d%d",&a,&b,&c);
    for(int i=0;i<110;i++)
    {
        for(int j=0;j<110;j++)
        {
            cup[i][j].x=i;
            cup[i][j].y=j;
            cup[i][j].sx=0;
            cup[i][j].sy=0;
            cup[i][j].v=0;
            cup[i][j].vis=0;
            cup[i][j].num=0;
        }
    }
    flag=0;
    bfs();
    return 0;
}

 

相关标签: BFS