【BFS】hdu 1973 Prime Path
题目描述：
中文大意：
使用两个锅，盛取定量水。
两个锅的容量和目标水量由用户输入。
允许的操作有：灌满锅、倒光锅内的水、一个锅中的水倒入另一个锅。
在两个锅互相倒水的过程中，若一个锅被倒满，而原来的锅中还有水，则剩余在原来的锅中。
不断执行这三个过程，直到任意一个锅中，贮存了目标数量的水，过程结束。
思路：
队列节点记录的是当前两个锅的贮水量和之前的一系列操作。
在弹出队列首节点，获取了当前两个锅的水量信息后，后续怎么操作，有 6 种选择：FILL(1)、FILL(2)、DROP(1)、DROP(2)、POUR(1,2)、POUR(2,1)。
注意：记得声明一个 visited[105][105] 数组，用来记录当前的情况是否出现过，若没有出现过，再将其压入队列，否则会超时。
代码：
#include<iostream>
#include<queue>
#include<string>
using namespace std;
int a,b,c;
struct node{
int x,y;
vector<string> msg;
node(int x, int y, vector<string> msg){
this->x = x;
this->y = y;
this->msg = msg;
};
node(int x, int y){
this->x = x;
this->y = y;
};
};
bool visited[105][105] = {false};
void bfs(){
node start = node(0, 0);
node next = node(0, 0);
visited[0][0] = true;
queue<node> q;
q.push(start);
while(!q.empty()){
start = q.front();
q.pop();
if(start.x == c || start.y == c){
int n = start.msg.size();
printf("%d\n", n);
for(int i=0;i<n;i++){
cout<<start.msg[i]<<endl;
}
return;
}
//FILL(1)
next = node(a, start.y, start.msg);
if(!visited[next.x][next.y]){
visited[next.x][next.y] = true;
next.msg.push_back("FILL(1)");
q.push(next);
}
//FILL(2)
next = node(start.x, b, start.msg);
if(!visited[next.x][next.y]){
visited[next.x][next.y] = true;
next.msg.push_back("FILL(2)");
q.push(next);
}
//DROP(1)
next = node(0, start.y, start.msg);
if(!visited[next.x][next.y]){
visited[next.x][next.y] = true;
next.msg.push_back("DROP(1)");
q.push(next);
}
//DROP(2)
next = node(start.x, 0, start.msg);
if(!visited[next.x][next.y]){
visited[next.x][next.y] = true;
next.msg.push_back("DROP(2)");
q.push(next);
}
//POUR(1,2)
int fill_num = b - start.y;
if(start.x >= fill_num){
next = node(start.x - fill_num, b, start.msg);
if(!visited[next.x][next.y]){
visited[next.x][next.y] = true;
next.msg.push_back("POUR(1,2)");
q.push(next);
}
}
else{
next = node(0, start.y + start.x, start.msg);
if(!visited[next.x][next.y]){
visited[next.x][next.y] = true;
next.msg.push_back("POUR(1,2)");
q.push(next);
}
}
//POUR(2,1)
fill_num = a - start.x;
if(start.y >= fill_num){
next = node(a, start.y - fill_num, start.msg);
if(!visited[next.x][next.y]){
visited[next.x][next.y] = true;
next.msg.push_back("POUR(2,1)");
q.push(next);
}
}
else{
next = node(start.x + start.y, 0, start.msg);
if(!visited[next.x][next.y]){
visited[next.x][next.y] = true;
next.msg.push_back("POUR(2,1)");
q.push(next);
}
}
}
printf("impossible\n");
}
int main(){
scanf("%d %d %d", &a, &b, &c);
bfs();
}
