首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >NYOJ 21 三个水杯(bfs模拟)

NYOJ 21 三个水杯(bfs模拟)

作者头像
Ch_Zaqdt
发布2019-01-10 11:16:48
4920
发布2019-01-10 11:16:48
举报
文章被收录于专栏:Zaqdt_ACMZaqdt_ACM

       这道题是一道bfs的题,主要是怎样把倒水的过程模拟出来,一共三个杯子,六种情况(A->B,A->C,B->A,B->C,C->A,C->B),所以我们可以用两个for循环模拟这六种情况。而在倒水的过程中又有两种情况,一是倒不满,二是倒完有剩余,这两种情况就需要判断一下了。还有就是标记数组开三维数组,用于标记每个杯子的状态。不太好想,建议结合代码手动模拟一下。

AC代码:

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct Node{
	int cup[3];
	int step;
}Now,Next;
int S[3],E[3],vis[105][105][105];        // 标记数组开大点
int bfs(){
	Now.cup[0] = S[0];
	Now.cup[1] = 0;
	Now.cup[2] = 0;
	Now.step = 0;
	vis[Now.cup[0]][Now.cup[1]][Now.cup[2]] = 1;         // 把初始状态标记
	queue<Node> q;
	q.push(Now);
	while(!q.empty()){
		Now = q.front();
		q.pop();
		if(Now.cup[0]==E[0]&&Now.cup[1]==E[1]&&Now.cup[2]==E[2]){
			return Now.step;
		}
		for(int i=0;i<3;i++){                //  用两个for循环模拟  从i->j倒水的过程
			for(int j=0;j<3;j++){
				if(i!=j){
					int water = S[j] - Now.cup[j];                 // water为这个杯子还能装多少水
					if(Now.cup[i]<water){                          // 判断这个杯子是否能倒满
						water = Now.cup[i];
					}
					Next = Now;                     // 及时初始化Next 否则只有一个杯子更新数据
					Next.cup[i] = Now.cup[i] - water;              // 从i被子里倒水
					Next.cup[j] = Now.cup[j] + water;							 // j杯子里加入这个多水
					if(vis[Next.cup[0]][Next.cup[1]][Next.cup[2]]==0){
						vis[Next.cup[0]][Next.cup[1]][Next.cup[2]] = 1;
						Next.step = Now.step + 1;
						q.push(Next);
					}
				}
			}
		}
	}
	return -1;
}
int main()
{
	int n;
	cin>>n;
	while(n--){
		memset(vis,0,sizeof(vis));
		cin>>S[0]>>S[1]>>S[2]>>E[0]>>E[1]>>E[2];
		if(E[0]+E[1]+E[2]!=S[0]){            // 剪枝
			cout<<"-1"<<endl;
		}
		else{
			cout<<bfs()<<endl;
		}
	}
	return 0;
}
/***
   [来源] NYOJ 21
	 [题目] 三个水杯
	 [思路]
	    用结构体存一个cup数组表示三个水杯,然后根据bfs搜索,用两个for循环模拟倒水的过程,
			剩下就是bfs过程,关键在于模拟倒水过程,详细看代码注释。
	 [输入]
	    2
			6 3 1
			4 1 1
			9 3 2
			7 1 1
	 [输出]
	    3
			-1
*/
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年02月06日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档