## Saturday, April 9, 2016

### Poj 3414 Pots - The White Belt - BFS

Poj 3414 Pots - The White Belt - 博客频道 - CSDN.NET
You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:
1. FILL(i)        fill the pot i (1 ≤ i ≤ 2) from the tap;
2. DROP(i)      empty the pot i to the drain;
3. POUR(i,j)    pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).
Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.
Input
On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).
Output
The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can't be achieved, the first and only line of the file must contain the word 'impossible'.
https://kartikkukreja.wordpress.com/2013/10/11/water-jug-problem/
The problem is solvable only when t is a multiple of gcd(a, b) and can be modeled as search through a state space. The state space for this problem can be described as the set of ordered pair of integers (x, y) such that x ∈ {0, 1, 2, …, a} and y ∈ {0, 1, 2, …, b}. The initial state is (0, 0) and the goal states are (t, y) and (x, t) ∀ x, y.
All we need now for a search procedure to work is a way to generate new states (successors) from a given state. This is captured by production rules that specify how and when a new state can be generated from a given state. For the water jug problem, the following production rules are sufficient:
1. (x, y) -> (a, y) if x < a i.e., Fill the first jug if it is not already full
2. (x, y) -> (x, b) if y < b i.e., Fill the second jug if it is not already full
3. (x, y) -> (0, y) if x > 0 i.e., Empty the first jug
4. (x, y) -> (x, 0) if y > 0 i.e, Empty the second jug
5. (x, y) -> (min(x + y, a), max(0, x + y – a)) if y > 0 i.e., Pour from second jug into first jug until the first jug is full or the second jug is empty
6. (x, y) -> (max(0, x + y – b), min(x + y, b)) if x > 0 i.e., Pour from first jug into second jug until the second jug is full or the first jug is empty
Strictly speaking, the conditions in the production rules are not required e.g., we could fill an already full jug except that it won’t lead us anywhere and would be wasteful in a tree search procedure where the visited states are not saved to prevent revisiting.
Now, a search procedure like BFS or DFS can be applied to systematically search from the initial state to one of the goal states through the state space.
https://github.com/kartikkukreja/blog-codes/blob/master/src/Water%20Jug%20Problem%20With%20BFS.cpp
// Representation of a state (x, y)
// x and y are the amounts of water in litres in the two jugs respectively
struct state {
int x, y;

// Used by map to efficiently implement lookup of seen states
bool operator < (const state& that) const {
if (x != that.x) return x < that.x;
return y < that.y;
}
};

// Capacities of the two jugs respectively and the target amount
int capacity_x, capacity_y, target;

void bfs(state start, stack <pair <state, int> >& path)   {
queue <state> q;
state goal = (state) {-1, -1};

// Stores seen states so that they are not revisited and
// maintains their parent states for finding a path through
// the state space
// Mapping from a state to its parent state and rule no. that
// led to this state
map <state, pair <state, int> > parentOf;

q.push(start);
parentOf[start] = make_pair(start, 0);

while (!q.empty())    {
// Get the state at the front of the queue
state top = q.front();
q.pop();

// If the target state has been found, break
if (top.x == target || top.y == target) {
goal = top;
break;
}

// Find the successors of this state
// This step uses production rules to prune the search space

// Rule 1: (x, y) -> (capacity_x, y) if x < capacity_x
// Fill the first jug
if (top.x < capacity_x)  {
state child = (state) {capacity_x, top.y};
// Consider this state for visiting only if it has not been visited before
if (parentOf.find(child) == parentOf.end()) {
q.push(child);
parentOf[child] = make_pair(top, 1);
}
}

// Rule 2: (x, y) -> (x, capacity_y) if y < capacity_y
// Fill the second jug
if (top.y < capacity_y)  {
state child = (state) {top.x, capacity_y};
if (parentOf.find(child) == parentOf.end()) {
q.push(child);
parentOf[child] = make_pair(top, 2);
}
}

// Rule 3: (x, y) -> (0, y) if x > 0
// Empty the first jug
if (top.x > 0)  {
state child = (state) {0, top.y};
if (parentOf.find(child) == parentOf.end()) {
q.push(child);
parentOf[child] = make_pair(top, 3);
}
}

// Rule 4: (x, y) -> (x, 0) if y > 0
// Empty the second jug
if (top.y > 0)  {
state child = (state) {top.x, 0};
if (parentOf.find(child) == parentOf.end()) {
q.push(child);
parentOf[child] = make_pair(top, 4);
}
}

// Rule 5: (x, y) -> (min(x + y, capacity_x), max(0, x + y - capacity_x)) if y > 0
// Pour water from the second jug into the first jug until the first jug is full
// or the second jug is empty
if (top.y > 0)  {
state child = (state) {min(top.x + top.y, capacity_x), max(0, top.x + top.y - capacity_x)};
if (parentOf.find(child) == parentOf.end()) {
q.push(child);
parentOf[child] = make_pair(top, 5);
}
}

// Rule 6: (x, y) -> (max(0, x + y - capacity_y), min(x + y, capacity_y)) if x > 0
// Pour water from the first jug into the second jug until the second jug is full
// or the first jug is empty
if (top.x > 0)  {
state child = (state) {max(0, top.x + top.y - capacity_y), min(top.x + top.y, capacity_y)};
if (parentOf.find(child) == parentOf.end()) {
q.push(child);
parentOf[child] = make_pair(top, 6);
}
}
}

if (goal.x == -1 || goal.y == -1)
return;

// backtrack to generate the path through the state space
path.push(make_pair(goal, 0));
// remember parentOf[start] = (start, 0)
while (parentOf[path.top().first].second != 0)
path.push(parentOf[path.top().first]);
}

int main()  {
stack <pair <state, int> > path;

printf("Enter the capacities of the two jugs : ");
scanf("%d %d", &capacity_x, &capacity_y);
printf("Enter the target amount : ");
scanf("%d", &target);

bfs((state) {0, 0}, path);
if (path.empty())
printf("\nTarget cannot be reached.\n");
else    {
printf("\nNumber of moves to reach the target : %d\nOne path to the target is as follows :\n", path.size() - 1);
while (!path.empty())   {
state top = path.top().first;
int rule = path.top().second;
path.pop();

switch (rule)   {
case 0: printf("State : (%d, %d)\n#\n", top.x, top.y);
break;
case 1: printf("State : (%d, %d)\nAction : Fill the first jug\n", top.x, top.y);
break;
case 2: printf("State : (%d, %d)\nAction : Fill the second jug\n", top.x, top.y);
break;
case 3: printf("State : (%d, %d)\nAction : Empty the first jug\n", top.x, top.y);
break;
case 4: printf("State : (%d, %d)\nAction : Empty the second jug\n", top.x, top.y);
break;
case 5: printf("State : (%d, %d)\nAction : Pour from second jug into first jug\n", top.x, top.y);
break;
case 6: printf("State : (%d, %d)\nAction : Pour from first jug into second jug\n", top.x, top.y);
break;
}
}
}
return 0;
}
http://www.acmerblog.com/POJ-3414-Pots-blog-1048.html
 `008` ` ``private` `static` `final` `String[] status = ``new` `String[] { ``""``, ``"FILL(1)"``,`
 `009` `    ``"FILL(2)"``, ``"DROP(1)"``, ``"DROP(2)"``, ``"POUR(1,2)"``, ``"POUR(2,1)"` `};`
 `010` ` ``private` `static` `boolean``[][] visted = ``new` `boolean``[``101``][``101``];`
 `011` ` ``private` `static` `int` `a;`
 `012` ` ``private` `static` `int` `b;`
 `013` ` ``private` `static` `int` `c;`
 `014`
 `015` ` ``public` `static` `void` `main(String[] args) {`
 `016` `    ``Scanner sc = ``new` `Scanner(System.in);`
 `017` `    ``for` `(``int` `i = ``0``; i < ``101``; ++i) {`
 `018` `        ``for` `(``int` `j = ``0``; j < ``101``; ++j)`
 `019` `            ``visted[i][j] = ``false``;`
 `020` `    ``}`
 `021` `    ``a = sc.nextInt();`
 `022` `    ``b = sc.nextInt();`
 `023` `    ``c = sc.nextInt();`
 `024` `    ``bfs();`
 `025` `  ``}`
 `026`
 `027` `  ``static` `void` `bfs() {`
 `028` `    ``boolean` `is = ``false``;`
 `029` `    ``LinkedList< Node> queue = ``new` `LinkedList< Node>();`
 `030` `    ``Node p = ``new` `Node();`
 `031` `    ``p.aa = ``0``;`
 `032` `    ``p.bb = ``0``;`
 `033` `    ``visted[p.aa][p.bb] = ``true``;`
 `034` `    ``queue.addLast(p);`
 `035`
 `042` `    ``while` `(!queue.isEmpty()) {`
 `043` `     ``Node front = queue.getFirst();`
 `044` `     ``queue.remove();`
 `045` `     ``int` `r = -``1``;`
 `046` `     ``for` `(``int` `i = ``1``; i <= ``6``; ++i) {`
 `047` `      ``int` `aa = front.aa;`
 `048` `      ``int` `bb = front.bb;`
 `049` `      ``int` `flag = i;`
 `050` `      ``switch` `(flag) {`
 `051` `       ``case` `1``:`
 `052` `        ``aa = a;`
 `053` `        ``break``;`
 `054` `       ``case` `2``:`
 `055` `        ``bb = b;`
 `056` `        ``break``;`
 `057` `       ``case` `3``:`
 `058` `        ``aa = ``0``;`
 `059` `        ``break``;`
 `060` `       ``case` `4``:`
 `061` `        ``bb = ``0``;`
 `062` `        ``break``;`
 `063` `       ``case` `5``:`
 `064` `        ``r = b - bb;`
 `065` `        ``bb = bb + (r <= aa ? r : aa);`
 `066` `        ``aa = (r <= aa ? (aa - r) : ``0``);`
 `067` `        ``break``;`
 `068` `       ``case` `6``:`
 `069` `        ``r = a - aa;`
 `070` `        ``aa = aa + (r <= bb ? r : bb);`
 `071` `        ``bb = (r <= bb ? (bb - r) : ``0``);`
 `072` `        ``break``;`
 `073` `       ``default``:`
 `074` `        ``break``;`
 `075` `       ``}`
 `076` `       ``if` `(aa == c || bb == c) {`
 `077` `        ``int` `size = front.status.size();`
 `078` `        ``System.out.println(size + ``1``);`
 `079` `        ``for` `(``int` `j = ``0``; j < size; ++j)`
 `080` `             ``System.out.println(status[front.status.get(j)]);`
 `081` `        ``System.out.println(status[flag]);`
 `082` `        ``is = ``true``;`
 `083` `        ``return``;`
 `084` `        ``}`
 `085` `        ``if` `(!visted[aa][bb]) {`
 `086` `         ``Node tmp = ``new` `Node();`
 `087` `         ``tmp.aa = aa;`
 `088` `         ``tmp.bb = bb;`
 `089` `         ``int` `size = front.status.size();`
 `090` `         ``for` `(``int` `j = ``0``; j < size; ++j)`
 `091` `            ``tmp.status.add(front.status.get(j));`
 `092` `         ``tmp.status.add(flag);`
 `093` `         ``visted[aa][bb] = ``true``;`
 `094` `         ``queue.addLast(tmp);`
 `095` `         ``}`
 `096` `     ``}`
 `097` `    ``}`
 `098` `    ``if` `(!is)`
 `099` `      ``System.out.println(``"impossible"``);`
 `100` ` ``}`
 `101`
 `102` ` ``private` `static` `class` `Node {`
 `103` `    ``private` `int` `aa;`
 `104` `    ``private` `int` `bb;`
 `105` `    ``private` `ArrayList< Integer> status = ``new` `ArrayList< Integer>();`
 `106` ` ``}`
http://www.cnblogs.com/java-home/archive/2012/03/10/2641524.html

X.DFS
https://github.com/kartikkukreja/blog-codes/blob/master/src/Water%20Jug%20Problem%20With%20DFS.cpp
void dfs(state start, stack <pair <state, int> >& path)   {
stack <state> s;
state goal = (state) {-1, -1};

// Stores seen states so that they are not revisited and
// maintains their parent states for finding a path through
// the state space
// Mapping from a state to its parent state and rule no. that
// led to this state
map <state, pair <state, int> > parentOf;

s.push(start);
parentOf[start] = make_pair(start, 0);

while (!s.empty())    {
// Get the state at the front of the stack
state top = s.top();
s.pop();

// If the target state has been found, break
if (top.x == target || top.y == target) {
goal = top;
break;
}

// Find the successors of this state
// This step uses production rules to produce successors of the current state
// while pruning away branches which have been seen before

// Rule 1: (x, y) -> (capacity_x, y) if x < capacity_x
// Fill the first jug
if (top.x < capacity_x)  {
state child = (state) {capacity_x, top.y};
// Consider this state for visiting only if it has not been visited before
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 1);
}
}

// Rule 2: (x, y) -> (x, capacity_y) if y < capacity_y
// Fill the second jug
if (top.y < capacity_y)  {
state child = (state) {top.x, capacity_y};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 2);
}
}

// Rule 3: (x, y) -> (0, y) if x > 0
// Empty the first jug
if (top.x > 0)  {
state child = (state) {0, top.y};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 3);
}
}

// Rule 4: (x, y) -> (x, 0) if y > 0
// Empty the second jug
if (top.y > 0)  {
state child = (state) {top.x, 0};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 4);
}
}

// Rule 5: (x, y) -> (min(x + y, capacity_x), max(0, x + y - capacity_x)) if y > 0
// Pour water from the second jug into the first jug until the first jug is full
// or the second jug is empty
if (top.y > 0)  {
state child = (state) {min(top.x + top.y, capacity_x), max(0, top.x + top.y - capacity_x)};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 5);
}
}

// Rule 6: (x, y) -> (max(0, x + y - capacity_y), min(x + y, capacity_y)) if x > 0
// Pour water from the first jug into the second jug until the second jug is full
// or the first jug is empty
if (top.x > 0)  {
state child = (state) {max(0, top.x + top.y - capacity_y), min(top.x + top.y, capacity_y)};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 6);
}
}
}

if (goal.x == -1 || goal.y == -1)
return;

// backtrack to generate the path through the state space
path.push(make_pair(goal, 0));
// remember parentOf[start] = (start, 0)
while (parentOf[path.top().first].second != 0)
path.push(parentOf[path.top().first]);
}
http://blog.csdn.net/u013446688/article/details/47949475