Pots——广度优先搜索+结构体数组

傷城~ 2022-07-10 13:28 149阅读 0赞

think:  
1今天上午AC了自己的第三道英文题，感觉和英文题目的距离不再那么遥远，而且自己在这个题目开始逐渐尝试学习使用C++编程，虽然只是头文件，但感觉自己不再那么畏惧，开始逐渐尝试战胜自己的畏惧，害怕难免会有，想起毕淑敏的一句话，你生而有翼，又何必匍匐前行，相信自己可以战胜自己的消极情绪，做一个积极向上的人，自己曾经考虑过用大学时光来写一本书，把自己的大学时光记录下来，或许，自己应该燃起曾经想过的希望，写一本自己的书，写一本平凡人的自传，或许我可以用这本书以记录我的编程时光为主，日后想想现在的自己，正如现在的自己想想高中的那些努力的时光，那种感动犹如阳光洒在自己的身上，暖暖的  
2回归题目，题意是我们有两个杯子A和B，需要盛C升水，有3种宏观操作，共包含6种详细操作，  
FILL：1>A归0，B不变 2>A不变，B归零  
DROP：1>A盛满，B不变 2>A不变，B盛满  
POUR：1>把A倒入B 2>把B倒入A  
注：POUR操作需要注意会不会有一个杯子会有水剩余

[sdut原题链接][sdut]

Pots  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:  
FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;  
DROP(i) empty the pot i to the drain;  
POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).  
Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

Input  
On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

Output  
The first line of the output must contain the length of the sequence of operations K. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Example Input  
3 5 4

Example Output  
6

Hint  
FILL(2)  
POUR(2,1)  
DROP(1)  
POUR(2,1)  
FILL(2)  
POUR(2,1)

Author

以下为accepted代码

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    using namespace std;
    
    int a, b, c, tp, op;
    int vis[104][104];
    struct node
    {
        int a;
        int b;
        int ans;
    }link[312];
    
    void FILL(int x, int y, int size, int l)
    {
        struct node f;
        if(l == 0)
        {
            f.a = a;
            f.b = y;
        }
        else if(l == 1)
        {
            f.a = x;
            f.b = b;
        }
        if(vis[f.a][f.b] == 0)
        {
            f.ans = size + 1;
            link[tp++] = f;
            vis[f.a][f.b] = 1;
        }
    }
    
    void DROP(int x, int y, int size, int l)
    {
        struct node f;
        if(l == 2)
        {
            f.a = 0;
            f.b = y;
        }
        else if(l == 3)
        {
            f.a = x;
            f.b = 0;
        }
        if(vis[f.a][f.b] == 0)
        {
            f.ans = size + 1;
            link[tp++] = f;
            vis[f.a][f.b] = 1;
        }
    }
    
    void POUR(int x, int y, int size, int l)
    {
        struct node f;
        if(l == 4)//a->b
        {
            if(x + y <= b)
            {
                f.a = 0;
                f.b = x + y;
            }
            else if(x + y > b)
            {
                f.a = x + y - b;
                f.b = b;
            }
        }
        else if(l == 5)//b->a
        {
            if(x + y <= a)
            {
                f.a = x + y;
                f.b = 0;
            }
            else if(x + y > a)
            {
                f.a = a;
                f.b = x + y -a;
            }
        }
        if(vis[f.a][f.b] == 0)
        {
            f.ans = size + 1;
            link[tp++] = f;
            vis[f.a][f.b] = 1;
        }
    }
    
    void BFS()
    {
        struct node t, f;
        tp = op = 0;
        memset(vis, 0, sizeof(vis));
        t.a = 0;
        t.b = 0;
        t.ans = 0;
        link[tp++] = t;
        vis[t.a][t.b] = 1;
        while(op < tp)
        {
            f = link[op++];
            if(f.a == c ||f.b == c)
            {
                printf("%d\n", f.ans);
                return;
            }
            for(int i = 0; i < 6; i++)
            {
                if(i == 0) FILL(f.a, f.b, f.ans, i);
                if(i == 1) FILL(f.a, f.b, f.ans, i);
                if(i == 2) DROP(f.a, f.b, f.ans, i);
                if(i == 3) DROP(f.a, f.b, f.ans, i);
                if(i == 4) POUR(f.a, f.b, f.ans, i);
                if(i == 5) POUR(f.a, f.b, f.ans, i);
            }
        }
        printf("impossible\n");
    }
    
    int main()
    {
        while(scanf("%d %d %d", &a, &b, &c) != EOF)
        {
            BFS();
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 200KB
    Submit time: 2017-02-17 11:44:12
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2012/pid/2780