poj 3414(简单bfs)
2024-10-21 09:47:08
题目链接：http://poj.org/problem?id=3414
思路：bfs简单应用，增对瓶A或者瓶B进行分析就可以了，一共6种状态。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std; struct Node{
int a,b,step;
char str[][];
}; int A,B,C;
bool mark[][];
bool bfs()
{
memset(mark,false,sizeof(mark));
queue<Node>que;
Node p,q;
p.a=,p.b=,p.step=;
que.push(p);
mark[][]=true;
while(!que.empty()){
p=que.front();
que.pop();
if(p.a==C||p.b==C){
printf("%d\n",p.step);
for(int i=;i<=p.step;i++){
printf("%s\n",p.str[i]);
}
return true;
}
if(p.a==){
q=p;
q.a=A;
q.step++;
strcpy(q.str[q.step],"FILL(1)");
if(!mark[q.a][q.b]){
mark[q.a][q.b]=true;
que.push(q);
}
}else if(p.a<=A){
q=p;
q.a=;
q.step++;
strcpy(q.str[q.step],"DROP(1)");
if(!mark[q.a][q.b]){
mark[q.a][q.b]=true;
que.push(q);
}
if(p.b<B){
q=p;
if(q.a+q.b<=B){
q.b+=q.a;
q.a=;
}else {
q.a=(q.b+q.a)-B;
q.b=B;
}
q.step++;
strcpy(q.str[q.step],"POUR(1,2)");
if(!mark[q.a][q.b]){
mark[q.a][q.b]=true;
que.push(q);
}
}
}
if(p.b==){
q=p;
q.b=B;
q.step++;
strcpy(q.str[q.step],"FILL(2)");
if(!mark[q.a][q.b]){
mark[q.a][q.b]=true;
que.push(q);
}
}else if(p.b<=B){
q=p;
q.b=;
q.step++;
strcpy(q.str[q.step],"DROP(2)");
if(!mark[q.a][q.b]){
mark[q.a][q.b]=true;
que.push(q);
}
if(p.a<A){
q=p;
if(q.b+q.a<=A){
q.a+=q.b;
q.b=;
}else {
q.b=(q.b+q.a)-A;
q.a=A;
}
q.step++;
strcpy(q.str[q.step],"POUR(2,1)");
if(!mark[q.a][q.b]){
mark[q.a][q.b]=true;
que.push(q);
}
}
}
}
return false;
} int main()
{
while(~scanf("%d%d%d",&A,&B,&C)){
if(!bfs())puts("impossible");
}
return ;
}
最新文章
- 移动端事件对象touches的误区
- 【DP】HIHO 1078
- 什么是闭包（closure），为什么要用它？
- php生成随机密码(php自定义函数)转自先锋教程网
- Scrapy安装、爬虫入门教程、爬虫实例（豆瓣电影爬虫）
- html19-----视频，音乐的插入
- mysql - 查看Port
- button 垂直分布
- python package的概念
- eclipse提升注解提示速度
- LeetCode 101. Symmetric Tree （对称树）
- Spring MVC的handlermapping之BeanNameUrlHandlerMapping初始化
- tf.nn.embedding_lookup TensorFlow embedding_lookup 函数最简单实例
- mac os x下的一些小技巧
- Spring Cloud构建微服务架构（二）服务消费者
- 读书笔记---HTML5实战 MARCO CASARIO（后六章）
- epoll+socket实现 socket并发 linux服务器
- CSRF 攻击（跨域攻击）
- C# 自定义配置文件
- Java之IO流总结
热门文章
- Android Exception 10(server)' ~ Channel is unrecoverably broken and will be disposed!)
- linux下的QQ执行玩法：pidgin-lwqq
- hibernate list和iterate
- Drupal如何集中控制静态变量？
- 解决chrome和firefox flash不透明的方法
- stl之hash_multiset
- ssh理论知识
- Python爬去图片实例,python 爬取图片
- 查询清除SQL Server数据库备份还原历史记录
- atitit.js的 字符串内容 转义  js处理html