> 题意：
> 给出两个容积分别为 a 和 b 的pot，按照以下三种操作方式，求出能否在一定步数后，使者两个pot的其中一个的水量为c。
>       1.FILL(i)：将ipot倒满水。
>       2.DROP(i)：将ipot倒空水。
>       3.POUR(i,j)： 将ipot的水倒到jpot上，直至要么ipot为空，要么jpot为满。
> 思路：
> BFS求最短路径步数，并在过程中利用回溯记录路径。
> #include <iostream>
> #include <queue>
> using namespace std;
> 
> int flag,path[1000];
> 
> struct pos
> {
>     int x;
>     int y;
>     int pathx;
>     int pathy;
>     int cdo;
>     int num;
>     int vis;
> }cp[110][110];
> 
> void init()
> {
>     for(int i = 0;i < 110;i++)
>         for(int j = 0;j < 110;j++)
>         {
>             cp[i][j].x = i;
>             cp[i][j].y = j;
>             cp[i][j].vis = 0;
>             cp[i][j].pathx = -1;
>             cp[i][j].pathy = -1;
>             cp[i][j].cdo = 0;
>             cp[i][j].num = 0;
>         }
>     flag = 0;
>     memset(path,-1,sizeof(path));
> }
> 
> int main()
> {
>     int a,b,c,cx,cy,i,ccx,ccy;
>     while(cin >> a >> b >> c)
>     {
>         init();
>         queue <pos> q;
>         q.push(cp[0][0]);
>         cp[0][0].vis = 1;
>         while(!q.empty())
>         {
>             pos front = q.front();
>             cx = front.x;
>             cy = front.y;
>             if(cx == c || cy == c)
>             {
>                 flag = 1;
>                 break;
>             }
>             q.pop();
>             if(!cp[a][cy].vis && cx >= 0 && cx <= a && cy >= 0 && cy <= b)
>             {
>                 q.push(cp[a][cy]);
>                 cp[a][cy].pathx = cx;
>                 cp[a][cy].pathy = cy;
>                 cp[a][cy].cdo = 2;
>                 cp[a][cy].num += cp[cx][cy].num + 1;
>                 cp[a][cy].vis = 1;
>             }
>             if(!cp[0][cy].vis && cx >= 0 && cx <= a && cy >= 0 && cy <= b)
>             {
>                 q.push(cp[0][cy]);
>                 cp[0][cy].pathx = cx;
>                 cp[0][cy].pathy = cy;
>                 cp[0][cy].cdo = 1;
>                 cp[0][cy].num += cp[cx][cy].num + 1;
>                 cp[0][cy].vis = 1;
>             }
>             if(!cp[cx][b].vis && cx >= 0 && cx <= a && cy >= 0 && cy <= b)
>             {
>                 q.push(cp[cx][b]);
>                 cp[cx][b].pathx = cx;
>                 cp[cx][b].pathy = cy;
>                 cp[cx][b].cdo = 4;
>                 cp[cx][b].num += cp[cx][cy].num + 1;
>                 cp[cx][b].vis = 1;
>             }
>             if(!cp[cx][0].vis && cx >= 0 && cx <= a && cy >= 0 && cy <= b)
>             {
>                 q.push(cp[cx][0]);
>                 cp[cx][0].pathx = cx;
>                 cp[cx][0].pathy = cy;
>                 cp[cx][0].cdo = 3;
>                 cp[cx][0].num += cp[cx][cy].num + 1;
>                 cp[cx][0].vis = 1;
>             }
>             if(cx + cy - b >= 0 && !cp[cx + cy - b][b].vis && cx >= 0 && cx <= a && cy >= 0 && cy <= b)
>             {
>                 q.push(cp[cx + cy - b][b]);
>                 cp[cx + cy - b][b].pathx = cx;
>                 cp[cx + cy - b][b].pathy = cy;
>                 cp[cx + cy - b][b].cdo = 5;
>                 cp[cx + cy - b][b].num += cp[cx][cy].num + 1;
>                 cp[cx + cy - b][b].vis = 1;
>             }
>             if(cx + cy - b < 0 && !cp[0][cx + cy].vis && cx >= 0 && cx <= a && cy >= 0 && cy <= b)
>             {
>                 q.push(cp[0][cx + cy]);
>                 cp[0][cx + cy].pathx = cx;
>                 cp[0][cx + cy].pathy = cy;
>                 cp[0][cx + cy].cdo = 5;
>                 cp[0][cx + cy].num += cp[cx][cy].num + 1;
>                 cp[0][cx + cy].vis = 1;
>             }
>             if(cx + cy - a >= 0 && !cp[a][cx + cy - a].vis && cx >= 0 && cx <= a && cy >= 0 && cy <= b)
>             {
>                 q.push(cp[a][cx + cy - a]);
>                 cp[a][cx + cy - a].pathx = cx;
>                 cp[a][cx + cy - a].pathy = cy;
>                 cp[a][cx + cy - a].cdo = 6;
>                 cp[a][cx + cy - a].num += cp[cx][cy].num + 1;
>                 cp[a][cx + cy - a].vis = 1;
>             }
>             if(cx + cy - a < 0 && !cp[cx + cy][0].vis && cx >= 0 && cx <= a && cy >= 0 && cy <= b)
>             {
>                 q.push(cp[cx + cy][0]);
>                 cp[cx + cy][0].pathx = cx;
>                 cp[cx + cy][0].pathy = cy;
>                 cp[cx + cy][0].cdo = 6;
>                 cp[cx + cy][0].num += cp[cx][cy].num + 1;
>                 cp[cx + cy][0].vis = 1;
>             }
>         }
>         while(!q.empty())   q.pop();
>         if(flag)
>         {
>             cout << cp[cx][cy].num << endl;
>             int cnum = cp[cx][cy].num;
>             for(i = cnum;i > 0;i--)
>             {
>                 path[i] = cp[cx][cy].cdo;
>                 ccx = cx;
>                 ccy = cy;
>                 cx = cp[ccx][ccy].pathx;
>                 cy = cp[ccx][ccy].pathy;
>             }
>             for(i = 1;i <= cnum;i++)
>             {
>                 if(path[i] == 1)    printf("DROP(%d)\n",1);
>                 if(path[i] == 2)    printf("FILL(%d)\n",1);
>                 if(path[i] == 3)    printf("DROP(%d)\n",2);
>                 if(path[i] == 4)    printf("FILL(%d)\n",2);
>                 if(path[i] == 5)    printf("POUR(%d,%d)\n",1,2);
>                 if(path[i] == 6)    printf("POUR(%d,%d)\n",2,1);
>             }
>         }
>         else
>             cout << "impossible" << endl;
>     }
>     return 0;
> }

• Re:BFS+回溯，贴代码，飘过~ (64) hrbust 2012-03-24 15:28:29
  • Re:BFS+回溯，贴代码，飘过~ (72) gagagahahaxixi 2015-09-02 23:05:26