题目

源地址：

http://poj.org/problem?id=3414

理解

因为卡一道题然后整整两天没有做题目什么的太不科学了- -。 纠结的难点在于，我怎么样把实现操作的路径打印出来。事实上，标记全部的六种状态，然后在bfs的过程中，把每一个状态全都输出到一个数组中去，然后再进行输出。

代码


#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <fstream>
#define debug puts("-----")
#define pi (acos(-1.0))
#define eps (1e-8)
#define inf (1<<28)
using namespace std;

const int maxn = 110;
int vis[maxn][maxn];
int a, b, c;
int step;
int flag;


struct Status
{
    int k1, k2;
    int op;
    int step;
    int pre;
} q[maxn *maxn];
int id[maxn *maxn];
int lastIndex;

void bfs()
{
    Status now, next;

    int head, tail;
    head = tail = 0;

    q[tail].k1 = 0; q[tail].k2 = 0;
    q[tail].op = 0; q[tail].step = 0; q[tail].pre = 0;

    tail++;

    memset(vis, 0, sizeof(vis));
    vis[0][0] = 1;

    while (head < tail)
    {
        now = q[head];
        head++;

        if (now.k1 == c || now.k2 == c)
        {
            flag = 1;
            step = now.step;
            lastIndex = head - 1;
        }

        for (int i = 1; i <= 6; i++)
        {
            if (i == 1)
            {
                next.k1 = a;
                next.k2 = now.k2;
            }
            else if (i == 2)
            {
                next.k1 = now.k1;
                next.k2 = b;
            }
            else if (i == 3)
            {
                next.k1 = 0;
                next.k2 = now.k2;
            }
            else if (i == 4)
            {
                next.k1 = now.k1;
                next.k2 = 0;
            }
            else if (i == 5)
            {
                if (now.k1 + now.k2 <= b)
                {
                    next.k1 = 0;
                    next.k2 = now.k1 + now.k2;
                }
                else
                {
                    next.k1 = now.k1 + now.k2 - b;
                    next.k2 = b;
                }
            }
            else if (i == 6)
            {
                if (now.k1 + now.k2 <= a)
                {
                    next.k1 = now.k1 + now.k2;
                    next.k2 = 0;
                }
                else
                {
                    next.k1 = a;
                    next.k2 = now.k1 + now.k2 - a;
                }
            }

            next.op = i;
            if (!vis[next.k1][next.k2])
            {
                vis[next.k1][next.k2] = 1;
                next.step = now.step + 1;
                next.pre = head - 1;

                q[tail].k1 = next.k1; q[tail].k2 = next.k2;
                q[tail].op = next.op; q[tail].step = next.step; q[tail].pre = next.pre;
                tail++;

                if (next.k1 == c || next.k2 == c)
                {
                    flag = 1;
                    step = next.step;
                    lastIndex = tail - 1;
                    return;
                }
            }
        }
    }


}

int main(int argc, char const *argv[])
{
    while (scanf("%d%d%d", &a, &b, &c) != EOF)
    {
        flag = 0;
        step = 0;

        bfs();
        if (flag)
        {
            printf("%d\n", step);

            id[step] = lastIndex;
            for (int i = step - 1; i >= 1; i--)
            {
                id[i] = q[id[i + 1]].pre;
            }

            for (int i = 1; i <= step; i++)
            {
                if (q[id[i]].op == 1)
                    printf("FILL(1)\n");

                else if (q[id[i]].op == 2)
                    printf("FILL(2)\n");

                else if (q[id[i]].op == 3)
                    printf("DROP(1)\n");

                else if (q[id[i]].op == 4)
                    printf("DROP(2)\n");

                else if (q[id[i]].op == 5)
                    printf("POUR(1,2)\n");

                else if (q[id[i]].op == 6)
                    printf("POUR(2,1)\n");
            }
        }
        else printf("impossible\n");
    }
    return 0;
}

更新日志

  • 2014年08月24日 已AC。