# Using BFS to solve the problem of backwater

## meaning of the title

Water pouring problem "fill A" means to fill cup A, "empty A" means to empty cup A, "pour A B" means to pour water of A into cup B and fill cup B or empty cup A.
Input
The input contains multiple sets of data. Each group of data input A, B, C data range 0 < A < = B, C < = B < = 1000, A and B mutual quality.
Output
The output of your program will consist of a series of instructions. These outputs will cause any tank to contain exactly C units of water. The last line of output for each set of data should be "success.". The output line starts at column 1 and should not have blank lines or any trailing spaces.
Sample Input
2 7 5
2 7 4
Sample Output
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
success

## thinking

According to the question, we know there are six operations:
fill A；
empty A；
pour A B；
fill B；
empty B；
pour B A；
At the beginning, we had two empty cups, using the above six operations to reach at least one cup containing C unit of water, so we didn't seem to have any idea.
Let's think about a simple maze path problem: starting from (0,0), you can move up, down, left and right in any direction without obstacles, and then continue to move at this point until you reach the end.
May refer to Using breadth first traversal search BFS to find the shortest path in matrix maze.
Compare these two questions:
A. B two empty cups -- > x, Y at the start of (0,0)
6 operations - > 4 directions
A. At least one cup in B contains C units of water -- > x, Y at the end of the maze
We can see that compared with the maze problem, this problem has two more operands and the judgment of the end point, so we can use the maze problem model to solve this problem;

## process

The whole process is to change the program of maze problem into the program of this problem:
Firstly, the Position data type in maze problem is changed to state data type of water A and B;

```struct state
{
int a;
int b;
bool operator < (const state &s) const
{//Note:
return a!=s.a?a<s.a:b<s.b;
}
};`
```

Let's change the up, down, left and right operations of maze problem to six operations of pouring water. See the code below for details.
The judgment of the end point is changed to:

```((now.a==C)||(now.b==C))
```

The rest can apply maze problem code template;

## Code

```#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
struct state
{
int a;
int b;
bool operator < (const state &s) const
{
return a!=s.a?a<s.a:b<s.b;
}
};
queue<state> q;
//The queue stores the states of A and B and finds the adjacent states
//Since the input of ontology is multiple groups of data recycling queues, it is a global variable
map<state, state> process;
//Similar to the storage path of maze problem, the content of next state saves the previous state
bool judgeState(state &s)
{//Compare maze problem to determine whether the point has been visited and whether it is out of bounds. This function determines whether the states in A and B have occurred
if(process.find(s)==process.end())
return false;
return true;
}
void print(state &p,int &A,int &B)
{
if(p.a==0&&p.b==0)
{//Recursive output
//	printf("%d,%d\n",p.a,p.b);
return ;
}
print(process[p],A,B);
string str;//Output operation
//Judge and output the change from the previous state to the next state judge operation output
//process stores the previous state p stores the current state
if(process[p].b==p.b&&process[p].a>p.a&&p.a==0)
str="empty A";
if(process[p].a==p.a&&p.b==0&&process[p].b>p.b)
str="empty B";
if(process[p].b==p.b&&process[p].a<p.a&&p.a==A)
str="fill A";
if(process[p].a==p.a&&process[p].b<p.b&&p.b==B)
str="fill B";
if(process[p].a<p.a&&process[p].b>p.b&&(p.a==A||p.b==0))
str="pour B A";
if(process[p].a>p.a&&process[p].b<p.b&&(p.a==0||p.b==B))
str="pour A B";
cout<<str<<endl;
//printf("%d,%d\n",p.a,p.b);
}
void BFS(int &A,int &B,int &C)
{//Apply BFS
state start {0,0};
q.push(start);//Start in queue
while(!q.empty())
{
state now=q.front();//Get current status (location)
q.pop();
//cout<<"----------"<<now.a<<" "<<now.b<<endl;
if((now.a==C)||(now.b==C))
{//Judge final state (end point)
print(now,A,B);
return;
}
state next;//Next state (next position)
//Fill a;
if(now.a < A)
{//If A is not empty, you can perform A full operation and B remains the same
next.a=A;
next.b=now.b;
if(!judgeState(next))
{//Judge whether the state has been reached (whether the point has been reached)
process[next]=now;  //The content stored in the next state is the previous state
q.push(next);
}
}
//The following operation notes are similar to filling A
//Fill b;
if(now.b < B)
{
next.b=B;
next.a=now.a;
if(!judgeState(next))
{
process[next]=now;
q.push(next);
}
}
//Empty a;
if(now.a > 0)
{//If A is not empty, A can be emptied, and B remains unchanged
next.a=0;
next.b=now.b;
if(!judgeState(next))
{
process[next]=now;
q.push(next);
}
}
//Empty b;
if(now.b> 0)
{
next.b=0;
next.a=now.a;
if(!judgeState(next))
{
process[next]=now;
q.push(next);
}
}
//Inverted b from a
if(now.a > 0)
{//From a to B, there are two results: A is emptied and B is full
//a empty
if(now.a+now.b<=B)
{//a=0 b=a+b B no overflow
next.a=0;
next.b=now.a+now.b;
if(!judgeState(next))
{
process[next]=now;
q.push(next);
}
}
//b full
if(now.b!=B)
{//B full A unfinished b=B a=A-(B-b)
next.a=now.a-(B-now.b);
next.b=B;
if(!judgeState(next))
{
process[next]=now;
q.push(next);
}
}
}
//Inverted a from b
if(now.b > 0)
{
//b empty
if(now.a+now.b <= A)
{
next.b=0;
next.a=now.a+now.b;
if(!judgeState(next))
{
process[next]=now;
q.push(next);
}
}
//a full
if(now.a!=A)
{
next.b=now.b-(A-now.a);
next.a=A;
if(!judgeState(next))
{
process[next]=now;
q.push(next);
}
}
}
}
}

int main()
{
int A,B,C;
while(scanf("%d %d %d",&A,&B,&C)!=EOF)
{
process.clear();//Reset state change per input (reset path)
while(!q.empty()) q.pop();  //Clear queue
BFS(A,B,C);
printf("success\n");
}
return 0;
}
```

## summary

This problem is very similar to the maze problem, which can be easily solved by applying code.
Attention shall be paid to the start and result states of six operations during BFS. When outputting, you should also pay attention to the comparison between the pre state and the post state to determine what operation is performed.

Published 2 original articles, praised 0 and visited 11

Keywords: REST

Added by Mr Camouflage on Tue, 03 Mar 2020 13:29:17 +0200