题意:给出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