B - Pour Water

倒水问题 “fill A” 表示倒满A杯,"empty A"表示倒空A杯,“pour A B” 表示把A的水倒到B杯并且把B杯倒满或A倒空。
Input
输入包含多组数据。每组数据输入 A, B, C 数据范围 0 < A <= B 、C <= B <=1000 、A和B互质。
Output
你的程序的输出将由一系列的指令组成。这些输出行将导致任何一个罐子正好包含C单位的水。每组数据的最后一行输出应该是“success”。输出行从第1列开始,不应该有空行或任何尾随空格。
Sample Input
2 7 5
2 7 4
Sample Output
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
success
Notes
如果你的输出与Sample Output不同,那没关系。对于某个"A B C"本题的答案是多解的,不能通过标准的文本对比来判定你程序的正确与否。 所以本题由 SPJ(Special Judge)程序来判定你写的代码是否正确。
解题思路
把A,B瓶水量作为状态,相当于迷宫问题中的每个点。初始状态下A,B瓶的v水量为0,0.每一次操作都会改变状态。总共有六次操作状态。使用bfs来进行搜索。每次操作后的状态记录在path数组。fill A时,当此时a中的水非满时,把a杯中的水置满,b杯中的水保持原样,入队列。fill B时,当此时b中的水非满时,把b杯中的水置满,a杯中的水保持原样,入队列。drop A时,把a中的水置空,b中的水不变,入队列。drop B时,把b中的水置空,a中的水不变,入队列。pour(a,b)时,此时需要分情况判断,如果a中的水大于b中剩余填满的水,就把b杯置满,否则就将a中的水倒入b中,a置空。pour(b,a)类似。
每bfs一次,就把当前操作对应的操作数记录在path数组中。

#include <iostream>
#include<stdio.h>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1500;
int a, b, c;
bool vis[MAXN+1][MAXN+1];
struct node {
        int a, b;
		int path[MAXN+1];
		int plen;

};
char path[6][20] = {

     "fill A"

    ,"fill B"

    ,"empty A"

    ,"empty B"

    ,"pour A B"

    ,"pour B A"

};
void output_result(int p[], int n)
{

    for(int i=0; i<n; i++)

        printf("%s\n",path[p[i]]);
        
        printf("success\n");

}
void bfs()
{
     queue<node> q;
     memset(vis, true, sizeof(vis));
      node f;
	f.a = 0;
	  f.b = 0;
     
      memset(f.path, 0, sizeof(f.path));
      f.plen = 0;
      q.push(f);
     vis[f.a][f.b] = false;
      while(!q.empty()) {
          f = q.front();
            q.pop();
         if(f.a == c || f.b == c) {
            output_result(f.path, f.plen);
                return;
         }
       node v;
        v = f;
         v.plen++;

        // FILL(a)
        if(a - f.a > 0) {
              v.a = a;

            v.b = f.b;

            if(vis[v.a][v.b]) {

                v.path[f.plen] = 0;

                q.push(v);

                vis[v.a][v.b] = false;

            }

        }

        // FILL(b)

        if(b - f.b > 0) {

            v.a = f.a;

            v.b = b;

            if(vis[v.a][v.b]) {

                v.path[f.plen] = 1;

                q.push(v);

               vis[v.a][v.b] = false;

            }

        }

        // DROP(a)

        if(f.a) {

            v.a = 0;

            v.b = f.b;

            if(vis[v.a][v.b]) {

                v.path[f.plen] = 2;

                q.push(v);

                vis[v.a][v.b] = false;

            }

        }

        // DROP(b)

        if(f.b) {

            v.a = f.a;

            v.b = 0;

            if(vis[v.a][v.b]) {

                v.path[f.plen] = 3;

                q.push(v);

                vis[v.a][v.b] = false;

            }

        }

        // POUR(a,b)

        if(f.a && (f.b < b)) {

            if(f.a > (b - f.b)) {

                v.a = f.a -(b - f.b);

                v.b = b;

            } else {

                v.a = 0;

                v.b = f.b + f.a;

            }

            if(vis[v.a][v.b]) {

                v.path[f.plen] = 4;

                q.push(v);

                vis[v.a][v.b] = false;

            }

        }

        // POUR(b,a)

        if(f.b && (f.a < a)) {

            if(f.b > (a - f.a)) {

                v.a = a;

                v.b = f.b -(a - f.a);

            } else {

                v.a = f.a + f.b;

                v.b = 0;

            }

            if(vis[v.a][v.b]) {

                v.path[f.plen] = 5;

                q.push(v);

               vis[v.a][v.b] = false;

            }

        }

    }
}
int main()
{
     while(scanf("%d%d%d",&a,&b,&c)!=EOF)
        bfs();   
   return 0;

}
上一篇:【翻译】.NET 6 中的 dotnet monitor


下一篇:在macOS Monterey上运行Android Device Monitor