题意：
给出两个容积分别为 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+回溯，贴代码，飘过~ (5569) 652107 2011-04-10 02:17:51
  • Re:BFS+回溯，贴代码，飘过~ (64) hrbust 2012-03-24 15:28:29
    • Re:BFS+回溯，贴代码，飘过~ (72) gagagahahaxixi 2015-09-02 23:05:26
• 主要是倒杯子麻烦。。BFS直接套就行 (0) ULTMaster 2014-08-04 21:21:57