poj 3414BFS问题_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > poj 3414BFS问题

poj 3414BFS问题

 2011/11/4 8:11:57  cavenkaka  http://cavenkaka.iteye.com  我要评论(0)
  • 摘要:题意:给出两个容积分别为a和b的pot,按照以下三种操作方式,求出能否在一定步数后,使者两个pot的其中一个的水量为c。1.FILL(i):将ipot倒满水。2.DROP(i):将ipot倒空水。3.POUR(i,j):将ipot的水倒到jpot上,直至要么ipot为空,要么jpot为满。思路:bfs求最短路径,与1426类似,只是每个节点的子节点数为6个而已。代码如下:#include<iostream>usingnamespacestd;constintMax=101
  • 标签:问题

?? 题意:给出两个容积分别为 a 和 b 的pot,按照以下三种操作方式,求出能否在一定步数后,使者两个pot的其中一个的水量为c。

????? 1.FILL(i):将ipot倒满水。

??????2.DROP(i):将ipot倒空水。

????? 3.POUR(i,j):?将ipot的水倒到jpot上,直至要么ipot为空,要么jpot为满。

? 思路:bfs求最短路径,与1426类似,只是每个节点的子节点数为6个而已。

代码如下:

#include<iostream>
using namespace std;
const int Max = 101;

 

struct node
{
    int ope;  int a;  int b;  node *pre;
}que[Max * Max];  //  队列结点,ope记录第几种操作,a,b记录此结点两个pot的水的数量。


bool vis[Max][Max];

char str[6][10] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};

 // 各操作对应输出的字符串。

 

int min(int a, int b)
{
    return a < b ? a : b;
}

 

void print(node now)
{
    if(now.pre != NULL)
	{
        print(*now.pre);
        cout << str[now.ope] << endl;
    }
}//递归输出答案个人认为写得很巧妙

 

void bfs(int a, int b, int c)
{
    int steps = 0;
    int head = 0, tail = 1;
    que[0].a = que[0].b = 0;
    que[0].pre = NULL; 
    while(tail - head > 0)
	{
        int count = tail - head;
        while(count --)//每一种情况都要考虑六种情况
		{
            node now = que[head];
            if(now.a == c || now.b == c)
			{
                cout << steps << endl;
                print(now);
                return;
            }
            if(!vis[a][now.b])
			{
                que[tail].ope = 0;
                que[tail].a = a;
                que[tail].b = now.b;
                que[tail].pre = &que[head];
                vis[a][now.b] = true;
                tail ++;
            }
            if(!vis[now.a][b])
			{
                que[tail].ope = 1;
                que[tail].a = now.a;
                que[tail].b = b;
                que[tail].pre = &que[head];
                vis[now.a][b] = true;
                tail ++;
            }
            if(!vis[0][now.b])
			{
                que[tail].ope = 2;
                que[tail].a = 0;
                que[tail].b = now.b;
                que[tail].pre = &que[head];
                vis[0][now.b] = true;
                tail ++;
            }
           if(!vis[now.a][0])
		   {
                que[tail].ope = 3;
                que[tail].a = now.a;
                que[tail].b = 0;
                que[tail].pre = &que[head];
                vis[now.a][0] = true;
                tail ++;
            }
            int wat1 = min(now.a, b - now.b);
            if(!vis[now.a - wat1][now.b + wat1])
			{
                que[tail].ope = 4;
                que[tail].a = now.a - wat1;
                que[tail].b = now.b + wat1;
                que[tail].pre = &que[head];
                vis[now.a - wat1][now.b + wat1] = true;
                tail ++;
            }
            int wat2 = min(a - now.a, now.b);
            if(!vis[now.a + wat2][now.b - wat2])
			{
                que[tail].ope = 5;
                que[tail].a = now.a + wat2;
                que[tail].b = now.b - wat2;
                que[tail].pre = &que[head];
                vis[now.a + wat2][now.b - wat2] = true;
                tail ++;
            }
            head ++;
        }
        steps ++;
    }
    cout << "impossible" << endl;
}

 

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    memset(vis, false, sizeof(vis));//初始化
    vis[0][0] = true;//初始化
    bfs(a, b, c);
    return 0;
}

?

?

发表评论
用户名: 匿名