首页 > 其他分享 >8.罐子(简单搜索 BFS最短步数+记录方案)

8.罐子(简单搜索 BFS最短步数+记录方案)

时间:2023-05-02 11:45:01浏览次数:52  
标签:罐子 int DROP POUR 最短 BFS 步数 FILL

罐子

↑ 题目链接

题目

给你两个罐子,容积分别为 \(A\) 升和 \(B\) 升。

现在,你可以进行如下三种操作:

FILL(i),将罐子 \(i(1≤i≤2)\) 灌满水。
DROP(i),将罐子 \(i(1≤i≤2)\) 清空。
POUR(i,j),将罐子 \(i\) 中的水倒向罐子 \(j\) ,直到罐子 \(i\) 空了或罐子 \(j\) 满了为止。
请问,至少多少次操作后,可以使得其中一个罐子里恰好有 \(C\) 升水。

输入格式

共一行,三个整数 A,B,C。

输出格式

如果无解,则输出一行 impossible 即可。

否则,第一行输出一个整数,表示最少操作次数。

随后按顺序每行输出一个操作指令,格式参考题面。

数据范围

\(1≤A,B,C≤100,C≤max(A,B)\)

输入样例:

3 5 4

输出样例:

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

思路

通过 \(BFS\) 搜索 \(6\) 种状态,记录最短步数即可

代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
string op[]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
int d[N][N];
int A,B,C;
struct Pos
{
	int x,y;
	string s;
};

void bfs()
{
	memset(d,-1,sizeof d);
	queue<Pos>q;
	q.push({0,0,""});
	d[0][0]=0;
	
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		if(t.x==C||t.y==C)
		{
            
			cout<<d[t.x][t.y]<<endl;//最少步数		
            
			for(auto x:t.s)//输出方案
			{
				cout<<op[x-'0']<<endl;
				
			}
			return;
		}
		
		int minx=min(t.x,B-t.y);
		int miny=min(A-t.x,t.y);
		//6种状态
		int dx[]={A,t.x,0,t.x,t.x-minx,t.x+miny};
		int dy[]={t.y,B,t.y,0,t.y+minx,t.y-miny};
		
		for(int i=0;i<6;i++)
		{
			int a=dx[i],b=dy[i];
			if(d[a][b]==-1)
			{ 
				d[a][b]=d[t.x][t.y]+1;
				q.push({a,b,t.s+to_string(i)});
			}
		}
	}
	
	puts("impossible");
}
int main()
{
	cin>>A>>B>>C;
	
	bfs();
	
	return 0;
}

标签:罐子,int,DROP,POUR,最短,BFS,步数,FILL
From: https://www.cnblogs.com/zzmxj/p/17367489.html

相关文章

  • 7.洗牌(简单搜索 BFS)
    洗牌↑题目链接题目给定两叠纸牌\(S1\)和\(S2\),每叠恰好有\(C\)张牌。每张牌的尺寸大小都完全相同,但是颜色可能不同。下面介绍洗牌规则。不妨设\(S1\)中纸牌从上到下编号依次为\(a_1,a_2,…,a_C\),\(S_2\)中纸牌从上到下编号依次为\(b_1,b_2,…,b_C\)。洗牌就......
  • 3.抓住那头牛(简单搜索 BFS)
    抓住那头牛↑题目链接题目农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点\(N\),牛位于点\(K\)。农夫有两种移动方式:从\(X\)移动到\(X−1\)或\(X+1\),每次移动花费一分钟从\(X\)移动到\(2∗X\),每次移动花费一分钟假设牛没有意识到农夫的行动,站......
  • 2.地牢大师(简单搜索 BFS)
    地牢大师↑题目链接题目你现在被困在一个三维地牢中,需要找到最快脱离的出路!地牢由若干个单位立方体组成,其中部分不含岩石障碍可以直接通过,部分包含岩石障碍无法通过。向北,向南,向东,向西,向上或向下移动一个单元距离均需要一分钟。你不能沿对角线移动,迷宫边界都是坚硬的岩石,你......
  • 最短路+二分题目整理
    前往奥格瑞玛的道路题目链接\(\qquad\)题目要求最小化最大费用,显然是使用二分答案,二分答案首先应该看限制和目标,此处的限制是血量限制,而目标是费用目标。这种情况我们可以二分费用,然后在图上跑最短路判定血量是否满足。\(\qquad\)对于check函数,我们去判定是否存在一条道路使得......
  • 「学习笔记」重修最短路
    \(u\)到\(v\)的最短路径的长度就是\(u\)到\(v\)的最短路。单源最短路算法可以求出一个点到其他点的最短路。全源最短路算法可以求出每一个点到其他各点的最短路。松弛操作:dis[v]=min(dis[v],dis[u]+w);。算法Floyd算法全源最短路算法,时间复杂度\(O_{n^3}\),......
  • BFS 简单应用
    前言:BFS即广度优先搜索(或宽度优先搜索),具体定义和实现不在赘述。本文所有代码前的开头头文件,宏定义和命名空间如下(只是一些常用的define和一个快读):#include<bits/stdc++.h>#defineTptemplate<typenameTy>#defineTstemplate<typenameTy,typename...Ar>#definell......
  • 最短路问题
    \[最短路\begin{cases}\单源最短路\quad\begin{cases}\所有边权都是正数\quad\begin{cases}\朴素Dijkstra算法\quad\\[3ex]堆优化版Dijkstra算法\quad\end{cases}\\\[5ex]存在负权边\quad\begin{cases}\Bell-Ford算法\quad\\[3ex]SPFA算法\quad\end{cases......
  • DataX-在Windows上实现postgresql同步数据到mysql
    场景DataX-阿里开源离线同步工具在Windows上实现Sqlserver到Mysql全量同步和增量同步:https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/130330353在上面实现sqlserver到mysql的数据同步之后,如果要实现postgresql到mysql数据同步流程一样。以PostGis中的OGC元数据......
  • 【LeeCode】934. 最短的桥 -- todo
    【题目描述】给你一个大小为 nxn 的二元矩阵 grid ,其中 1 表示陆地,0 表示水域。岛 是由四面相连的 1 形成的一个最大组,即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。你可以将任意数量的 0 变为 1 ,以使两座岛连接起来,变成 一座岛 。返回必须......
  • 【优化指派】基于禁忌搜索算法求解指派优化问题(耗时最短)附Matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......