Directed Graph PDF

https://thejeshvenkata.github.io/HTMLPages/water-jug-problem-u...
Water Jug problem using BFS

You are given a m litre jug and a n litre jug . Both the jugs are initially empty. The
jugs don’t have markings to allow measuring smaller quantities. You have to use
the jugs to measure d litres of water where d is less than n.
(X, Y) corresponds to a state where X refers to amount of water in Jug1 and Y
refers to amount of water in Jug2
Determine the path from initial state (xi, yi) to final state (xf, yf), where (xi, yi) is (0,
0) which indicates both Jugs are initially empty and (xf, yf) indicates a state
which could be (0, d) or (d, 0).
The operations you can perform are:
1. Empty a Jug, (X, Y)->(0, Y) Empty Jug 1
2. Fill a Jug, (0, 0)->(X, 0) Fill Jug 1
3. Pour water from one jug to the other until one of the jugs is either empty or
full, (X, Y) -> (X-d, Y+d)
Examples:
Input : 4 3 2
Output : {(0, 0), (0, 3), (4, 0), (4, 3),
(3, 0), (1, 3), (3, 3), (4, 2),
(0, 2)}
Recommended: Please try your approach on {IDE}

first, before moving on to the solution.
We have discussed one solution in The Two Water Jug Puzzle (two-water-jug-
puzzle.html)
In this post a BFS (breadth-first-traversal-for-a-graph.html) based solution is
discussed.
We run breadth first search on the states and these states will be created after
applying allowed operations and we also use visited map of pair to keep track
of states that should be visited only once in the search.This solution can also be
achieved using depth first search.
1 of 5 24/04/19, 1:40 am
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
using namespace std;
void BFS(int a, int b, int target)

{
// Map is used to store the states, every
// state is hashed to binary value to
// indicate either that state is visited
// before or not
map<pii, int> m;
bool isSolvable = false;
vector<pii> path;
queue<pii> q; // queue to maintain states

q.push({ 0, 0 }); // Initialing with initial state
while (!q.empty()) {
pii u = q.front(); // current state
q.pop(); // pop off used state
// if this state is already visited

if (m[{ u.first, u.second }] == 1)
continue;
// doesn't met jug constraints

if ((u.first > a || u.second > b ||
u.first < 0 || u.second < 0))
continue;
// filling the vector for constructing

// the solution path
path.push_back({ u.first, u.second });
// marking current state as visited

m[{ u.first, u.second }] = 1;
// if we reach solution state, put ans=1

if (u.first == target || u.second == target) {
isSolvable = true;
if (u.first == target) {
if (u.second != 0)
// fill final state

path.push_back({ u.first, 0 });
}
else {
if (u.first != 0)
// fill final state

path.push_back({ 0, u.second });
}
// print the solution path

int sz = path.size();
for (int i = 0; i < sz; i++)
2 of 5 24/04/19, 1:40 am
cout << "(" << path[i].first

<< ", " << path[i].second << ")\n";
break;
}
// if we have not reached final state

// then, start developing intermediate
// states to reach solution state
q.push({ u.first, b }); // fill Jug2
q.push({ a, u.second }); // fill Jug1
for (int ap = 0; ap <= max(a, b); ap++) {
// pour amount ap from Jug2 to Jug1

int c = u.first + ap;
int d = u.second - ap;
// check if this state is possible or not

if (c == a || (d == 0 && d >= 0))
q.push({ c, d });
// Pour amount ap from Jug 1 to Jug2

c = u.first - ap;
d = u.second + ap;
// check if this state is possible or not

if ((c == 0 && c >= 0) || d == b)
q.push({ c, d });
}
q.push({ a, 0 }); // Empty Jug2

q.push({ 0, b }); // Empty Jug1
}
// No, solution exists if ans=0

if (!isSolvable)
cout << "No solution";
}
// Driver code
int main()
{
int Jug1 = 4, Jug2 = 3, target = 2;
cout << "Path from initial state "
"to solution state :\n";
BFS(Jug1, Jug2, target);
return 0;
}
Output:
3 of 5 24/04/19, 1:40 am
Path from initial state to solution state ::

(0, 0)
(0, 3)
(4, 0)
(4, 3)
(3, 0)
(1, 3)
(3, 3)
(4, 2)
(0, 2)
This article is contributed by

Abhishek rajput
. If you like GeeksforGeeks and would like to contribute, you can also write an
article using
contribute.geeksforgeeks.org
or mail your article to [email protected]. See your article appearing
on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Practice Tags :
Article Tags :
Graph
BFS
Please write to us at [email protected] to report any issue with the
above content.
Recommended Posts:
The Two Water Jug Puzzle (two-water-jug-puzzle.html)

Number of cyclic elements in an array where we can jump according to value (number-of-cyclic-
elements-in-an-array-where-we-can-jump-according-to-value.html)
Water Jug problem using BFS (water-jug-problem-using-bfs.html)
Degree Centrality (Centrality Measure) (degree-centrality-centrality-measure.html)
Shortest path to reach one prime to other by changing single digit at a time (shortest-path-reach-one-
prime-changing-single-digit-time.html)
Topological Sorting (topological-sorting.html)
Multi Source Shortest Path in Unweighted Graph (multi-source-shortest-path-in-unweighted-
4 of 5 24/04/19, 1:40 am
graph.html)
Proof that Hamiltonian Path is NP-Complete (proof-hamiltonian-path-np-complete.html)
Number of Transpositions in a Permutation (number-of-transpositions-in-a-permutation.html)
Number of single cycle components in an undirected graph (number-of-simple-cyclic-components-in-
an-undirected-graph.html)
Post navigation
<< Previous Post (number-of-cyclic-elements-in-an-array-where-we-can-jump-
according-to-value.html) Next Post >> (degree-centrality-centrality-
measure.html)
(
Login
to Rate)
3.8 Average Difficulty : 3.8/5.0

Based on 6 vote(s)
Basic Easy Medium Hard Expert
Add to TODO List
Mark as DONE
Writing code in comment? Please use

ide.geeksforgeeks.org
, generate link and share the link here.
Load Comments Share this post!
5 of 5 24/04/19, 1:40 am

Directed Graph PDF

Uploaded by

Copyright:

Available Formats

Directed Graph PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Directed Graph PDF

Uploaded by

Copyright:

Available Formats

https://thejeshvenkata.github.io/HTMLPages/water-jug-problem-u...

Water Jug problem using BFS

Recommended: Please try your approach on {IDE}

void BFS(int a, int b, int target)

queue<pii> q; // queue to maintain states

pii u = q.front(); // current state

q.pop(); // pop off used state

// if this state is already visited

// doesn't met jug constraints

// filling the vector for constructing

// marking current state as visited

// if we reach solution state, put ans=1

// fill final state

// fill final state

// print the solution path

cout << "(" << path[i].first

// if we have not reached final state

for (int ap = 0; ap <= max(a, b); ap++) {

// pour amount ap from Jug2 to Jug1

// check if this state is possible or not

// Pour amount ap from Jug 1 to Jug2

// check if this state is possible or not

q.push({ a, 0 }); // Empty Jug2

// No, solution exists if ans=0

Path from initial state to solution state ::

This article is contributed by

The Two Water Jug Puzzle (two-water-jug-puzzle.html)

3.8 Average Difficulty : 3.8/5.0

Basic Easy Medium Hard Expert

Add to TODO List

Writing code in comment? Please use

Load Comments Share this post!

You might also like