倒水问题 C/C++实现方法

本文主要是介绍倒水问题 C/C++实现方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

倒水问题：
给定 2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出 L 升的水，如果可以，输出步骤，如果不可以，请输出 No Solution

二、解题思路

这个题刚开始一点想法都没有，原本把这当成一个数学问题来想（就那种纯数学），后来突然想起来这个是在搜索算法下的一个实验题，于是我开始往这方面靠，搜索算法，我首先想到的就是DFS和BFS，这道题我就是用BFS来解决的。

我们首先想这个是否真的符合BFS来解决呢，其实分析不难发现，对于两个杯子倒水问题其实也就是8种情况，而且每一步都是这8种情况，那这样其实就有点符合BFS算法来找路径了。

假设有两个杯子为X，Y其实每一步都是固定的在进行操作，一共有八种操作：
（1）把X装满
（2）把Y装满
（3）把X倒空
（4）把Y倒空
（5）X向Y中倒水，X倒完，Y没有被装满
（6）X向Y中倒水，Y被装满
（7）Y向X中倒水，Y倒完，X没有被装满
（7）Y向X中倒水，X被装满。
废话不多说直接上代码

三、代码

int x,y,L;
struct pool{int x,y;string s;
}current;
queue<pool> q;
bool visited[100][100];
string BFS()
{q.push(current);visited[current.x][current.y] = 1;while(!q.empty())//队列中还有元素{current=q.front();q.pop();if(current.x == L || current.y == L)return current.s;if(!visited[x][current.y])//把X装满{current.x = x;current.s += "把x装满\n";visited[current.x][current.y] = 1;q.push(current);}if(!visited[current.x][y])//把Y装满{current.y = y;current.s+="把Y装满\n";visited[current.x][current.y] = 1;q.push(current);}if(!visited[0][current.y])//把X倒空{current.x = 0;current.s+="把x倒空\n";visited[current.x][current.y] = 1;q.push(current);}if(!visited[current.x][0])//把y倒空{current.y = 0;current.s += "把y倒空\n";visited[current.x][current.y] = 1;q.push(current);}if((current.x + current.y <= y) && !visited[0][current.y + current.x])//把x中的水倒入y中，x倒完，y没有被装满{current.y = current.x + current.y;current.x = 0;current.s += "把x中的水倒入y中，x倒完，y没有被装满\n";visited[current.x][current.y] = 1;q.push(current);}if((current.x + current.y > y) && !visited[current.x + current.y - y][y])//把x倒入y中，y被装满{current.x = current.x + current.y - y;current.y = y;current.s+="把x倒入y中，y被装满\n";visited[current.x][current.y] = 1;q.push(current);}if((current.x + current.y <= x) && !visited[current.x + current.y][0])//把y中的水倒入x中，y倒完，x没有被装满{current.x = current.x + current.y;current.y = 0;current.s+= "把y中的水倒入x中，y倒完，x没有被装满\n";visited[current.x][current.y] = 1;q.push(current);} else if((current.x + current.y > x) && !visited[x][current.y + current.x - x])//把y倒入x中，x被倒满{current.y = current.x + current.y - x;current.x = x;current.s+="把y倒入x中，x被倒满\n";visited[current.x][current.y] = 1;q.push(current);}}return "No Solution";
}