No46-【原】-计算机算法设计与分析-三个水杯倒水问题

文章目录

1. 1. 题目来源
2. 2. 问题描述
3. 3. 输入
4. 4. 输出
5. 5. 样例输入
6. 6. 样例输出
7. 7. C++实现
8. 8. 感谢

题目来源

南阳理工学院OJ:http://acm.nyist.net/JudgeOnline/problem.php?pid=21

问题描述

给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。

输入

输入数据由input.txt给出.
测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 v3="">0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态

输出

输出到文件output.txt中
如果能够达到目标状态输出true,达不到输出false

样例输入

input.txt

6 3 1
4 1 1

样例输出

output.txt

true

C++实现

/*
* @Author: Scott Wang
* @Date:   2016-04-15 21:36:02
* @Last Modified by:   Scott Wang
* @Last Modified time: 2016-04-15 23:08:34
*/

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>

using namespace std;

struct Node
{
    int id;                     //当前节点在vector中的位置
    int current[3];         //当前３个水杯中的水量
    int step;                   //已走的步数
    int father;                 //标记上一步
};

void input();
bool bfs();
void printStep(int id);
void output2Terminal(bool result);
void output(bool result);

int work[6][2] = {{0, 1}, {0, 2}, {1, 0}, {1, 2}, {2, 0}, {2, 1}};

int src[3];
int des[3];
vector<Node> v;

int main()
{
    bool result;

    // 初始化数据
    input();

    // 进行广度优先遍历
    result = bfs();

    // 在控制台输出结果
    output2Terminal(result);

    // 输出结果到output.txt
    output(result);

    return 0;
}

/**
 * 初始化杯子的容量和目标水量
 */
void input()
{
    ifstream input("input.txt", ios::in);
    if (!input.is_open())
    {
        cerr << "Can't open input.txt" << endl;
        exit(-1);
    }

    input >> src[0] >> src[1] >> src[2];
    input >> des[0] >> des[1] >> des[2];

    input.close();
}

/**
 * 进行广度优先遍历
 * @return 判断结果
 */
bool bfs()
{
    int front = 0, rear = 0;
    bool foot[100][100][100] = {0};
    Node temp = {0, {src[0], 0, 0}, 0, -1};
    foot[temp.current[0]][temp.current[1]][temp.current[2]] = true;
    v.push_back(temp);
    rear++;
    int index = 0;
    while (front < rear)
    {
        index++;
        temp = v[front++];
        if (temp.current[0] == des[0] &&
                temp.current[1] == des[1] &&
                temp.current[2] == des[2] )
        {
            return true;
        }
        for (int i = 0; i < 6; i++)
        {
            Node temp1 = temp;
            temp1.step++;
            temp1.father = temp.step;
            int s = work[i][0], d = work[i][1];
            int available = src[d] - temp1.current[d];

            if (0 == temp1.current[s] || 0 == available)
            {
                continue;
            }

            if (temp1.current[s] <= available)
            {
                temp1.current[d] += temp1.current[s];
                temp1.current[s] = 0;
            }
            else
            {
                temp1.current[s] -= available;
                temp1.current[d] = src[d];
            }
            if (!foot[temp1.current[0]][temp1.current[1]][temp1.current[2]])
            {
                temp1.id = v.size() - 1;
                v.push_back(temp1);
                rear++;
                foot[temp1.current[0]][temp1.current[1]][temp1.current[2]] = true;
            }
        }
    }

    return false;
}

/**
 * 输出倒水的步骤
 */
void printStep(int id)
{
    if (id)
    {
        printStep(v[id].father);
    }
    cout << v[id].current[0] << "\t" << v[id].current[1] << "\t" << v[id].current[2] << endl;
}

/**
 * 输出结果到控制台
 * @param result 结果
 */
void output2Terminal(bool result)
{
    if (result)
    {
        cout << "共需" << v.back().step << "次" << endl;
        cout << "步骤为：" << endl;
        printStep(v.size() - 1);
    }
    else
    {
        cout << "此题无解" << endl;
    }
}

/**
 * 返回结果 - 是否找到满足条件的倒法
 * @param result 结果 true or false
 */
void output(bool result)
{
    ofstream output("output.txt", ios::out);
    if (!output.is_open())
    {
        cerr << "Can't open output.txt" << endl;
        exit(-1);
    }

    output << (result ? "true" : "false") << endl;

    output.close();
}

感谢

感谢访问我的个人博客的朋友，如果您感觉本站对您搜索的问题有所帮助，并感觉对本站还满意的话，顶一下吧，希望您把本站分享给您的朋友！在此对您表示由衷的谢意！ :)