Notes

// water jug problem:
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

void printpath(map<pii, pii> mp, pii u)

{

if (u.first == 0 && u.second == 0) {

cout << 0 << " " << 0 << endl;

return;

}

printpath(mp, mp[u]);

cout << u.first << " " << u.second << endl;

}

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

{

map<pii, int> m;

bool isSolvable = false;

map<pii, pii> mp;

queue<pii> q;

q.push(make_pair(0, 0));

while (!q.empty()) {

auto pii u = q.front();

q.pop();

if (m[u] == 1)

continue;

if ((u.first > a || u.second > b || u.first < 0

|| u.second < 0))

continue;

m[{ u.first, u.second }] = 1;

if (u.first == target || u.second == target) {

isSolvable = true;

printpath(mp, u);

if (u.first == target) {

if (u.second != 0)

cout << u.first << " " << 0 << endl; }

else {

if (u.first != 0)

cout << 0 << " " << u.second << endl;

}

return;

}

if (m[{ u.first, b }] != 1) {

q.push({ u.first, b });

mp[{ u.first, b }] = u;

}

if (m[{ a, u.second }] != 1) {

q.push({ a, u.second });

mp[{ a, u.second }] = u;

}

int d = b - u.second;

if (u.first >= d) {

int c = u.first - d;

if (m[{ c, b }] != 1) {

q.push({ c, b });

mp[{ c, b }] = u;

}

}

else {

int c = u.first + u.second;

if (m[{ 0, c }] != 1) {

q.push({ 0, c });

mp[{ 0, c }] = u;

}

}

d = a - u.first;

if (u.second >= d) {

int c = u.second - d;

if (m[{ a, c }] != 1) {

q.push({ a, c });

mp[{ a, c }] = u;

}

}

else {

int c = u.first + u.second; if (m[{ c, 0 }] != 1) {

q.push({ c, 0 });

mp[{ c, 0 }] = u;

}

}

if (m[{ u.first, 0 }] != 1) {

q.push({ u.first, 0 });

mp[{ u.first, 0 }] = u;

}

if (m[{ 0, u.second }] != 1) {

q.push({ 0, u.second });

mp[{ 0, u.second }] = u;

}

}

if (!isSolvable)

cout << "No solution";

}

int main()

{

int Jug1 = 4, Jug2 = 3, target = 2;

cout << "Path from initial state "

"to solution state ::n";

BFS(Jug1, Jug2, target);

return 0;

}


// dfs search
#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX 5

struct Vertex {

char label;

bool visited;

};

//stack variables

int stack[MAX];

int top = -1;

//graph variables

//array of vertices

struct Vertex* lstVertices[MAX];

//adjacency matrix

int adjMatrix[MAX][MAX];

//vertex count

int vertexCount = 0;

//stack functions

void push(int item) {

stack[++top] = item;

}

int pop() {

return stack[top--];

}

int peek() { return stack[top];

}

bool isStackEmpty() {

return top == -1;

}

//graph functions

//add vertex to the vertex list

void addVertex(char label) {

struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));

vertex->label = label;

vertex->visited = false;

lstVertices[vertexCount++] = vertex;

}

//add edge to edge array

void addEdge(int start,int end) {

adjMatrix[start][end] = 1;

adjMatrix[end][start] = 1;

}

//display the vertex

void displayVertex(int vertexIndex) {

printf("%c ",lstVertices[vertexIndex]->label);

}

//get the adjacent unvisited vertex

int getAdjUnvisitedVertex(int vertexIndex) {

int i;

for(i = 0; i < vertexCount; i++) {

if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) {

return i;

}

}

return -1;

} void depthFirstSearch() {

int i;

//mark first node as visited

lstVertices[0]->visited = true;

//display the vertex

displayVertex(0);

//push vertex index in stack

push(0);

while(!isStackEmpty()) {

//get the unvisited vertex of vertex which is at top of the stack

int unvisitedVertex = getAdjUnvisitedVertex(peek());

//no adjacent vertex found

if(unvisitedVertex == -1) {

pop();

} else {

lstVertices[unvisitedVertex]->visited = true;

displayVertex(unvisitedVertex);

push(unvisitedVertex);

}

}

//stack is empty, search is complete, reset the visited flag

for(i = 0;i < vertexCount;i++) {

lstVertices[i]->visited = false;

}

}

int main() {

int i, j;

for(i = 0; i < MAX; i++) { // set adjacency

for(j = 0; j < MAX; j++) // matrix to 0

adjMatrix[i][j] = 0;

} addVertex('S'); // 0

addVertex('A'); // 1

addVertex('B'); // 2

addVertex('C'); // 3

addVertex('D'); // 4

addEdge(0, 1); // S - A

addEdge(0, 2); // S - B

addEdge(0, 3); // S - C

addEdge(1, 4); // A - D

addEdge(2, 4); // B - D

addEdge(3, 4); // C - D

printf("Depth First Search: ");

depthFirstSearch();

return 0;

}