題目描述

有一個很大的水缸和二個容量分別為X和Y的水壺，按照以下的規則倒水，問最少經幾次倒水后，可得到Z升水
規則1：水缸向水壺1倒水，將水壺1裝滿；
規則2：水缸向水壺2倒水，將水壺2裝滿；
規則3：水壺1向水缸倒水，直到水壺1空；
規則4：水壺2向水缸倒水，直到水壺2空；
規則5：水壺1向水壺2倒水，直到水壺1空了或者水壺2滿了；
規則6：水壺2向水壺1倒水，直到水壺2空了或者水壺1滿了；

輸入

只有一行數據，包括以空格分隔的三個數字，分別表示水壺1( <= 100)、 水壺2的水量( <= 100 )以及期望得到的水量( <=100 )。

輸出

若經若干次倒水能得到所要求的水量，則輸出最少的倒水次數；若無論如何倒水都無法得到規定的水量，則輸出No Solution!

樣例輸入

4 3 1

樣例輸出

2

AC代碼

#include <iostream> #include <string.h> using namespace std; struct point //結構體 {int x, y, step; }; bool used[101][101]; point q[20000], s; int xx, yy, t; int f = 1, e = 1; point gen(point u, int cc)//嘗試枚舉每一個規則 {point v = u;v.step = u.step + 1;//開始枚舉規則if (cc == 1) v.x = xx;//水缸向水壺1倒水，將水壺1裝滿else if (cc == 2) v.y = yy;//水缸向水壺2倒水，將水壺2裝滿else if (cc == 3) v.x = 0;//水壺1向水缸倒水，直到水壺1空else if (cc == 4) v.y = 0;//水壺2向水缸倒水，直到水壺2空else if (cc == 5)//水壺1向水壺2倒水，直到水壺1空了或者水壺2滿了{if (u.x + u.y <= yy) v.x = 0, v.y = u.x + u.y;//如果y能把x和y的水量都裝下else v.y = yy, v.x = u.x + u.y - yy;//y裝不下從x倒過來的水}else//水壺2向水壺1倒水，直到水壺2空了或者水壺1滿了{if (u.x + u.y <= xx) v.y = 0, v.x = u.x + u.y;//如果x能把x和y的水量都裝下else v.x = xx, v.y = u.x + u.y - xx;//x裝不下從y倒過來的水}return v; } int main() {scanf ("%d %d %d", &xx, &yy, &t);//xx是x桶的水量,yy是y桶的水量if (t == 0){printf ("0\n");return 0;}memset (used, 0, sizeof (used));//memsets.x = 0, s.y = 0, s.step = 0;q[1] = s; ///開始寬搜///while (f <= e)//f是出隊下標 e是入隊下標{point u = q[f++];//選定的元素for (int i = 1; i <= 6; i++)//嘗試枚舉6個規則{point v = gen(u, i);//v就是將要入隊的元素if (used[v.x][v.y] == 0){if (v.x == t || v.y == t)//任意一個杯子里面有目標水量{printf ("%d\n", v.step);//就打印步數return 0;//默默退出}q[++e] = v;//入隊used[v.x][v.y] = 1;//表示已經被選擇過}}}printf ("No Solution!\n");//如果無法完成return 0; }

思路分析

step1:將初始狀態入隊
step2:以初始狀態為中心按6個規則向6個方向尋找可能的值入隊
step3:在通過可能的值向6個方向繼續拓展,直到找到目標(水壺1 或 水壺2 中的水 等于目標水量)

轉載于:https://www.cnblogs.com/LJA001162/p/11218432.html

總結

以上是生活随笔為你收集整理的c++ 宽搜(倒水)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。