状态搜索,每种状态下面共有六种选择,将搜索到的状态保存即可。
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带你飞]专题一的更多相关文章
-
POJ - 2251 bfs [kuangbin带你飞]专题一
立体bfs,共有六个方向: const int dx[] = {0,0,1,-1,0,0}; const int dy[] = {1,-1,0,0,0,0}; const int dz[] = {0, ...
-
POJ - 3984 bfs [kuangbin带你飞]专题一
bfs搜索过程中将路径保存下即可. AC代码 #include<cstdio> #include<cstring> #include<algorithm> #inc ...
-
HDU - 3533 bfs [kuangbin带你飞]专题二
看了好久的样例才看懂. 题意:有一个人要从(0,0)走到(n,m),图中有k个碉堡,每个碉堡可以向某个固定的方向每隔t秒放一次炮,炮弹不能穿越另一个碉堡,会被阻挡.人在移动的过程中不会被炮弹打到,也就 ...
-
HDU - 2102 A计划 (BFS) [kuangbin带你飞]专题二
思路:接BFS判断能否在限制时间内到达公主的位置,注意如果骑士进入传送机就会被立即传送到另一层,不会能再向四周移动了,例如第一层的位置(x, y, 1)是传送机,第二层(x, y, 2)也是传送机,这 ...
-
UVA - 11624 多点bfs [kuangbin带你飞]专题一
题意:某人身陷火场,总有k个点着火,着火点可向四周扩散,问此人能否逃离. 思路:可能有多个着火点,以这些着火点作为起点进行bfs,得到整个火场的最短距离,然后又以人所在坐标作为起点进行bfs,得到该人 ...
-
FZU - 2150 bfs [kuangbin带你飞]专题一
题意:两个人玩很变态的游戏,将一个草坪的某两个点点燃,点燃的草坪可以向上下左右四个方向扩散,问能否将整块草坪上面的草都点燃.如果能,输出最短时间(^_^他们就能玩更变态的游戏了),如果不能,输出-1. ...
-
HDU - 2612 bfs [kuangbin带你飞]专题一
分别以两个人的家作为起点,bfs求得到每个KFC最短距离.然后枚举每个KFC,求得时间之和的最小值即可. 此题不符合实际情况之处: 通过了一个KFC再去另一个KFC可以吗? 出题人都没好好想过吗? ...
-
HDU - 1495 bfs [kuangbin带你飞]专题一
模拟倒水的过程,每次可以把第i个杯子的水向第j个杯子里面倒,这可能出现新的状态,不停的更新状态,指导某两个杯子的水等于S/2说明找到答案,如果所有状态搜索完毕仍然不能均分,则退出. 注意:如果S是奇数 ...
-
POJ - 3087 模拟 [kuangbin带你飞]专题一
模拟洗牌的过程,合并两堆拍的方式:使先取s2,再取s1:分离成两堆的方式:下面C张放到s1,上面C张到s2.当前牌型与第一次相同时,说明不能搜索到答案. AC代码 #include<cstdio ...
随机推荐
-
iOS进阶_FMDB的简单使用
先引入FMDB第三方,点击查看方法 一.创建表 1.创建sql语句 NSString *createSql = @"create table if not exists t_stude ...
-
C# 获取wave文件信息【转】
public class WaveHelper { /// <summary> /// 数据流 /// </summary> private Stream m_WaveData ...
-
scroll、offset和client的区别
整体布局: <!DOCTYPE> <head> <meta http-equiv="Content-Type" content="text/ ...
-
android平台手电筒开发源代码
android平台手电筒开发源代码,AndroidManifest.xml文件的入口是startapp,这个文件没上传上来,大家可以自己写. 1. [代码]android 1 2 3 4 5 6 7 ...
-
Stream Collector
// Accumulate names into a List List<String> list = people.stream().map(Person::getName).colle ...
-
OpenCV之mixChannels()函数使用说明
step 1: 函数功能说明 mixChannels主要就是把输入的矩阵(或矩阵数组)的某些通道拆分复制给对应的输出矩阵(或矩阵数组)的某些通道中,其中的对应关系就由fromTo参数制定. step ...
-
rm -vf `ls |egrep -v "info_20130826-180233.31764|QueryParser.INFO"`
> rm -vf `ls |egrep -v "info_20130826-180233.31764|QueryParser.INFO"`
-
SQL语句 不足位数补0
select RIGHT('0000'+CAST( '123' AS nvarchar(50)),4) DWBH 公式 RIGHT('位数'+CAST(要判断的字段 AS nvarchar(50)) ...
-
(转)Vi命令详解
vi编辑器是所有Unix及Linux系统下标准的编辑器,它的强大不逊色于任何最新的文本编辑器,这里只是简单地介绍一下它的用法和一小部分指令.由于对Unix及Linux系统的任何版本,vi编辑器是完全相 ...
-
基于 Vue.js 的移动端组件库mint-ui实现无限滚动加载更多
通过多次爬坑,发现了这些监听滚动来加载更多的组件的共同点, 因为这些加载更多的方法是绑定在需要加载更多的内容的元素上的, 所以是进入页面则直接触发一次,当监听到滚动事件之后,继续加载更多, 所以对于无 ...