[转帖]poj3414倒水问题_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  Android, Python及开发编程讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 3769 | 回复: 0   主题: [转帖]poj3414倒水问题        上一篇   下一篇 
    本主题由 Administrator 于 2019-9-10 20:51:19 移动
HogarTron
注册用户
等级:新兵
经验:66
发帖:2
精华:0
注册:2017-3-9
状态:离线
发送短消息息给HogarTron 加好友    发送短消息息给HogarTron 发消息
发表于: IP:您无权察看 2019-9-10 15:06:55 | [全部帖] [楼主帖] 楼主

题意:给出a,b两个水杯的容量,和一个要达到的水量c。总共3种操作,两个杯子那就是六种。要求通过这六种操作来时两个杯子其中有一个水量为c的最少操作数。

解题思路:这道题用到的是广搜bfs,水量(i,j)代表一个点,通过这六种操作可以变成另一个点,那么这两个点之间就是有路的,每个点有没有访问过用邻接矩阵vis【i】【j】存储。

代码如下:

#include<iostream>
#include<queue>
#include<cstdlib>
#include<cstring>
#define N 105
using namespace std;
int a, b, c;
int vis[N][N];
struct node {
int a,b;
char path[N];
int plen;
char path[6][10] = {
"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"
void out( char p[], int n)
cout << n << endl;
for (int i = 0;i < n;i++)
cout <<path[p[i]] << endl;
void bfs()
queue<node>q;
memset(vis, 0, sizeof(vis));
node f;
f.a = 0;
f.b = 0;
memset(f.path, 0, sizeof(f.path));
f.plen = 0;
q.push(f);
vis[f.a][f.b] = 1;
while (!q.empty())
f = q.front();
q.pop();
if (f.a == c || f.b == c)
out( f.path, f.plen);
return;
node v;
v = f;
v.plen++;
//fill(a)
if (a - f.a > 0)
v.a = a;
v.b = f.b;
if (!vis[v.a][v.b])
v.path[f.plen] = 0;
q.push(v);
vis[v.a][v.b] = 0;
//fill(b)
if (b - f.b > 0)
v.a = f.a;
v.b = b;
if (!vis[v.a][v.b])
v.path[f.plen] = 1;
q.push(v);
vis[v.a][v.b] = 1;
//drop(a)
if (f.a)
v.a = 0;
v.b = f.b;
if (!vis[v.a][v.b])
v.path[f.plen] = 2;
q.push(v);
vis[v.a][v.b] = 1;
//drop(b)
if (f.b)
v.a = f.a;
v.b = 0;
if (!vis[v.a][v.b])
v.path[f.plen] = 3;
q.push(v);
vis[v.a][v.b] = 1;
//pour(a,b)
if (f.a && (f.b < b))
if (f.a > (b - f.b))//倒满a有剩余
v.b = b;
v.a = f.a + f.b - b;
else
v.a = 0;
v.b = f.a + f.b;
if (!vis[v.a][v.b])
v.path[f.plen] = 4;
q.push(v);
vis[v.a][v.b] = 1;
//pour(b,a)
if (f.b && (a > f.a))
if (f.b > (a - f.a))
v.a = a;
v.b = f.a + f.b - a;
else
v.b = 0;
v.a = f.a + f.b;
if (!vis[v.a][v.b])
v.path[f.plen] = 5;
q.push(v);
vis[v.a][v.b] = 1;
cout << "impossible" << endl;
int main()
cin >> a >> b >> c;
bfs();
return 0;


该贴由system转至本版2019-9-10 20:51:18




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论