POJ - 3414 bfs [kuangbin带你飞]专题一

时间:2022-05-17 22:38:41

状态搜索,每种状态下面共有六种选择,将搜索到的状态保存即可。

d[i][j]表示状态A杯中水i升,B杯中水j升,总状态数量不会超过A杯的容量 * B杯的容量。

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 100 + 5;

struct node{
	int A, B; //当前状态
	string op;
	node(){
	}
	node(int a, int b, string op):A(a), B(b), op(op){
	}
}pre[maxn][maxn];

int d[maxn][maxn], a, b, c;

void print(int x, int y){
	//printf("%d %d\n", x, y);
	int px = pre[x][y].A, py = pre[x][y].B;
	if(px == -1 && py == -1) return;
	print(px, py);
	cout << pre[x][y].op << endl;
}

int bfs(){
	int cup[] = {a, b};
	memset(d, -1, sizeof(d));
	d[0][0] = 0;
	queue<node>q;
	q.push(node(0, 0, ""));
	pre[0][0] = node(-1, -1, "");
	while(!q.empty()) {
		node p = q.front();
		q.pop();
		if(p.A == c || p.B == c){
			printf("%d\n", d[p.A][p.B]);
			print(p.A, p.B);
			return 1;
		}
		int w[] = {p.A, p.B};
		for(int i = 0; i < 2; ++i)
			for(int j = 0; j < 2; ++j) {
				if(i == j) continue;
				//Fill
				w[0] = p.A, w[1] = p.B;
				w[i] = cup[i];
				if(d[w[0]][w[1]] == -1) {
					d[w[0]][w[1]] = d[p.A][p.B] + 1;
					string op = "";
					if(i == 0) op = "FILL(1)";
					else op = "FILL(2)";
					q.push(node(w[0], w[1], ""));
					pre[w[0]][w[1]] = node(p.A, p.B, op);
				}

				//Drop
				w[0] = p.A, w[1] = p.B;
				w[i] = 0;
				if(d[w[0]][w[1]] == -1) {
					d[w[0]][w[1]] = d[p.A][p.B] + 1;
					string op = "";
					if(i == 0) op = "DROP(1)";
					else op = "DROP(2)";
					q.push(node(w[0], w[1], ""));
					pre[w[0]][w[1]] = node(p.A, p.B, op);
				}

				//Pour
				w[0] = p.A, w[1] = p.B;
				int pour = min(w[i], cup[1 - i] - w[1 - i]);
				w[i] -= pour, w[1 -i] += pour;
				if(d[w[0]][w[1]] == -1) {
				d[w[0]][w[1]] = d[p.A][p.B] + 1;
					string op = "";
					if(i == 0) op = "POUR(1,2)";
					else op = "POUR(2,1)";
					q.push(node(w[0], w[1], ""));
					pre[w[0]][w[1]] = node(p.A, p.B, op);
			}
		}
	}
	return 0;
}

int main(){
	while(scanf("%d%d%d", &a, &b, &c) == 3){
		if(!bfs()) printf("impossible\n");
	}
	return 0;
}

如有不当之处欢迎指出!

POJ - 3414 bfs [kuangbin带你飞]专题一的更多相关文章

  1. POJ - 2251 bfs &lbrack;kuangbin带你飞&rsqb;专题一

    立体bfs,共有六个方向: const int dx[] = {0,0,1,-1,0,0}; const int dy[] = {1,-1,0,0,0,0}; const int dz[] = {0, ...

  2. POJ - 3984 bfs &lbrack;kuangbin带你飞&rsqb;专题一

    bfs搜索过程中将路径保存下即可. AC代码 #include<cstdio> #include<cstring> #include<algorithm> #inc ...

  3. HDU - 3533 bfs &lbrack;kuangbin带你飞&rsqb;专题二

    看了好久的样例才看懂. 题意:有一个人要从(0,0)走到(n,m),图中有k个碉堡,每个碉堡可以向某个固定的方向每隔t秒放一次炮,炮弹不能穿越另一个碉堡,会被阻挡.人在移动的过程中不会被炮弹打到,也就 ...

  4. HDU - 2102 A计划 &lpar;BFS&rpar; &lbrack;kuangbin带你飞&rsqb;专题二

    思路:接BFS判断能否在限制时间内到达公主的位置,注意如果骑士进入传送机就会被立即传送到另一层,不会能再向四周移动了,例如第一层的位置(x, y, 1)是传送机,第二层(x, y, 2)也是传送机,这 ...

  5. UVA - 11624 多点bfs &lbrack;kuangbin带你飞&rsqb;专题一

    题意:某人身陷火场,总有k个点着火,着火点可向四周扩散,问此人能否逃离. 思路:可能有多个着火点,以这些着火点作为起点进行bfs,得到整个火场的最短距离,然后又以人所在坐标作为起点进行bfs,得到该人 ...

  6. FZU - 2150 bfs &lbrack;kuangbin带你飞&rsqb;专题一

    题意:两个人玩很变态的游戏,将一个草坪的某两个点点燃,点燃的草坪可以向上下左右四个方向扩散,问能否将整块草坪上面的草都点燃.如果能,输出最短时间(^_^他们就能玩更变态的游戏了),如果不能,输出-1. ...

  7. HDU - 2612 bfs &lbrack;kuangbin带你飞&rsqb;专题一

    分别以两个人的家作为起点,bfs求得到每个KFC最短距离.然后枚举每个KFC,求得时间之和的最小值即可. 此题不符合实际情况之处:  通过了一个KFC再去另一个KFC可以吗? 出题人都没好好想过吗? ...

  8. HDU - 1495 bfs &lbrack;kuangbin带你飞&rsqb;专题一

    模拟倒水的过程,每次可以把第i个杯子的水向第j个杯子里面倒,这可能出现新的状态,不停的更新状态,指导某两个杯子的水等于S/2说明找到答案,如果所有状态搜索完毕仍然不能均分,则退出. 注意:如果S是奇数 ...

  9. POJ - 3087 模拟 &lbrack;kuangbin带你飞&rsqb;专题一

    模拟洗牌的过程,合并两堆拍的方式:使先取s2,再取s1:分离成两堆的方式:下面C张放到s1,上面C张到s2.当前牌型与第一次相同时,说明不能搜索到答案. AC代码 #include<cstdio ...

随机推荐

  1. iOS进阶&lowbar;FMDB的简单使用

    先引入FMDB第三方,点击查看方法 一.创建表 1.创建sql语句    NSString *createSql = @"create table if not exists t_stude ...

  2. C&num; 获取wave文件信息【转】

    public class WaveHelper { /// <summary> /// 数据流 /// </summary> private Stream m_WaveData ...

  3. scroll、offset和client的区别

    整体布局: <!DOCTYPE> <head> <meta http-equiv="Content-Type" content="text/ ...

  4. android平台手电筒开发源代码

    android平台手电筒开发源代码,AndroidManifest.xml文件的入口是startapp,这个文件没上传上来,大家可以自己写. 1. [代码]android 1 2 3 4 5 6 7 ...

  5. Stream Collector

    // Accumulate names into a List List<String> list = people.stream().map(Person::getName).colle ...

  6. OpenCV之mixChannels&lpar;&rpar;函数使用说明

    step 1: 函数功能说明 mixChannels主要就是把输入的矩阵(或矩阵数组)的某些通道拆分复制给对应的输出矩阵(或矩阵数组)的某些通道中,其中的对应关系就由fromTo参数制定. step ...

  7. rm -vf &grave;ls &vert;egrep -v "info&lowbar;20130826-180233&period;31764&vert;QueryParser&period;INFO"&grave;

    > rm -vf `ls |egrep -v "info_20130826-180233.31764|QueryParser.INFO"`

  8. SQL语句 不足位数补0

    select RIGHT('0000'+CAST( '123'  AS nvarchar(50)),4) DWBH 公式 RIGHT('位数'+CAST(要判断的字段 AS nvarchar(50)) ...

  9. (转)Vi命令详解

    vi编辑器是所有Unix及Linux系统下标准的编辑器,它的强大不逊色于任何最新的文本编辑器,这里只是简单地介绍一下它的用法和一小部分指令.由于对Unix及Linux系统的任何版本,vi编辑器是完全相 ...

  10. 基于 Vue&period;js 的移动端组件库mint-ui实现无限滚动加载更多

    通过多次爬坑,发现了这些监听滚动来加载更多的组件的共同点, 因为这些加载更多的方法是绑定在需要加载更多的内容的元素上的, 所以是进入页面则直接触发一次,当监听到滚动事件之后,继续加载更多, 所以对于无 ...