Te dan una jarra de m litro y una jarra de litro. Ambas jarras están inicialmente vacías. Las jarras no tienen marcas para permitir medir cantidades más pequeñas. Tienes que usar las jarras para medir d litros de agua donde d es menor que n.
(X, Y) corresponde a un estado donde X se refiere a la cantidad de agua en la Jarra 1 e Y se refiere a la cantidad de agua en la Jarra 2
Determine el camino desde el estado inicial (xi, yi) hasta el estado final (xf, yf) , donde (xi, yi) es (0, 0) lo que indica que ambas jarras están inicialmente vacías y (xf, yf) indica un estado que podría ser (0, d) o (d, 0).
Las operaciones que puede realizar son:
- Vaciar una jarra, (X, Y)->(0, Y) Vaciar jarra 1
- Llena una jarra, (0, 0)->(X, 0) Llena la jarra 1
- Vierta agua de una jarra a la otra hasta que una de las jarras esté vacía o llena, (X, Y) -> (Xd, Y+d)
Ejemplos:
Input : 4 3 2 Output : {( 0,0),(0,3),(4,0),(4,3),(3,0),(1,3),(3,3),(4,2),(0,2)}
Hemos discutido la solución óptima en El rompecabezas de dos jarras de agua . En esta publicación, se analiza una solución basada en BFS .
Aquí, seguimos explorando todos los diferentes casos válidos de los estados del agua en la jarra simultáneamente hasta que alcancemos el agua objetivo requerida.
Como se indica en el enunciado del problema, en cualquier estado dado podemos realizar cualquiera de las siguientes operaciones:
- llenar una jarra
- vaciar una jarra
- Transfiere agua de una jarra a otra hasta que cualquiera de ellas se llene por completo o se vacíe.
Ejecución del algoritmo:
Comenzamos en un estado inicial en la cola donde ambas jarras están vacías. Luego continuamos explorando todos los posibles estados intermedios derivados del estado de jarra actual utilizando las operaciones provistas.
También mantenemos una array de estados visitados para evitar volver a visitar el mismo estado de jarras una y otra vez.
Casos | Jarra 1 | Jarra 2 | Es válida |
---|---|---|---|
Caso 1 | Llenarlo | vaciarlo | ✔ |
Caso 2 | vaciarlo | Llenarlo | ✔ |
Caso 3 | Llenarlo | Llenarlo | Caso redundante |
Caso 4 | vaciarlo | vaciarlo | Ya visitado (Estado inicial) |
Caso 5 | Sin alterar | Llenarlo | ✔ |
Caso 6 | Llenarlo | Sin alterar | ✔ |
Caso 7 | Sin alterar | Vacío | ✔ |
Caso 8 | Vacío | Sin alterar | ✔ |
Caso 9 | Transferir agua de este | Transferir agua a este | ✔ |
Caso 10 | Transferir agua a este | Transferir agua de este | ✔ |
En la tabla de arriba, podemos observar que el estado en el que ambas jarras están llenas es redundante , ya que no podremos continuar/hacer nada con este estado de ninguna manera posible.
Entonces, procedemos, teniendo en cuenta todos los casos de estado válidos (como se muestra en la tabla anterior) y hacemos un BFS sobre ellos.
En el BFS, primero omitimos los estados que ya se visitaron o si la cantidad de agua en cualquiera de las jarras excedió la cantidad de la jarra.
Si continuamos más, primero marcamos el estado actual como visitado y verificamos si en este estado, si hemos obtenido la cantidad de agua objetivo en cualquiera de las jarras, podemos vaciar la otra jarra y devolver todo el camino del estado actual.
Pero, si aún no hemos encontrado la cantidad objetivo, derivamos los estados intermedios del estado actual de las jarras, es decir, derivamos los casos válidos, mencionados en la tabla anterior (revise el código una vez si tiene alguna confusión).
Seguimos repitiendo todos los pasos anteriores hasta que hayamos encontrado nuestro objetivo o no queden más estados para continuar.
Implementación:
Java
//Java program for water jug problem //using BFS //Code by: Sparsh_CBS import java.util.*; class Pair{ int j1, j2; List<Pair> path; Pair(int j1, int j2){ this.j1 = j1; this.j2 = j2; path = new ArrayList<>(); } Pair(int j1, int j2, List<Pair> _path){ this.j1 = j1; this.j2 = j2; path = new ArrayList<>(); path.addAll(_path); path.add(new Pair(this.j1,this.j2)); } } public class GFG{ public static void main(String[] args) throws java.lang.Exception{ int jug1 = 4; int jug2 = 3; int target = 2; getPathIfPossible(jug1, jug2, target); } private static void getPathIfPossible(int jug1, int jug2, int target){ boolean[][] visited = new boolean[jug1+1][jug2+1]; Queue<Pair> queue = new LinkedList<>(); //Initial State: Both Jugs are empty so, //initialise j1 j2 as 0 and put it in the path list Pair initialState = new Pair(0,0); initialState.path.add(new Pair(0,0)); queue.offer(initialState); while(!queue.isEmpty()){ Pair curr = queue.poll(); //Skip already visited states and overflowing water states if(curr.j1 > jug1 || curr.j2 > jug2 || visited[curr.j1][curr.j2]) continue; //mark current jugs state as visited visited[curr.j1][curr.j2] = true; //Check if current state has already reached //the target amount of water or not if(curr.j1 == target || curr.j2 == target){ if(curr.j1 == target){ //If in our current state, jug1 holds the //required amount of water, then we empty the jug2 //and push it into our path. curr.path.add(new Pair(curr.j1,0)); } else{ //else, If in our current state, jug2 holds the //required amount of water, then we empty the jug1 //and push it into our path. curr.path.add(new Pair(0,curr.j2)); } int n = curr.path.size(); System.out.println("Path of states of jugs followed is :"); for(int i = 0; i < n; i++) System.out.println(curr.path.get(i).j1+" , "+curr.path.get(i).j2); return; } //If we have not yet found the target, then we have three cases left //I. Fill the jug and Empty the other //II. Fill the jug and let the other remain untouched //III. Empty the jug and let the other remain untouched //IV. Transfer amounts from one jug to another //Please refer to the table attached above to understand //the cases that we are taking into consideration //Now, //I. Fill the jug and Empty the other queue.offer(new Pair(jug1, 0, curr.path)); queue.offer(new Pair(0, jug2, curr.path)); //II. Fill the jug and let the other remain untouched queue.offer(new Pair(jug1, curr.j2, curr.path)); queue.offer(new Pair(curr.j1, jug2, curr.path)); //III. Empty the jug and let the other remain untouched queue.offer(new Pair(0, curr.j2, curr.path)); queue.offer(new Pair(curr.j1, 0, curr.path)); //IV. Transfer water from one to another until one jug becomes empty //or until one jug becomes full in this process //Transferring water form jug1 to jug2 int emptyJug = jug2-curr.j2; int amountTransferred = Math.min(curr.j1, emptyJug); int j2 = curr.j2+amountTransferred; int j1 = curr.j1-amountTransferred; queue.offer(new Pair(j1, j2,curr.path)); //Tranferring water form jug2 to jug1 emptyJug = jug1-curr.j1; amountTransferred = Math.min(curr.j2, emptyJug); j2 = curr.j2-amountTransferred; j1 = curr.j1+amountTransferred; queue.offer(new Pair(j1, j2,curr.path)); } System.out.println("Not Possible to obtain target"); } }
C++
#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 u =q.front(); // cout<<u.first<<" "<<u.second<<endl; q.pop(); if(m[u]==1) continue; if ((u.first > a || u.second > b || u.first < 0 || u.second < 0)) continue; // cout<<u.first<<" "<<u.second<<endl; 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; } // completely fill the jug 2 if(m[{u.first,b}]!=1) {q.push({u.first,b}); mp[{u.first,b}]=u;} // completely fill the jug 1 if(m[{a,u.second}]!=1) { q.push({a,u.second}); mp[{a,u.second}]=u;} //transfer jug 1 -> jug 2 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;} } //transfer jug 2 -> jug 1 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;} } // empty the jug 2 if(m[{u.first,0}]!=1) { q.push({u.first,0}); mp[{u.first,0}]=u;} // empty the jug 1 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; }
Python3
from collections import deque def BFS(a, b, 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 m = {} isSolvable = False path = [] # Queue to maintain states q = deque() # Initialing with initial state q.append((0, 0)) while (len(q) > 0): # Current state u = q.popleft() #q.pop() #pop off used state # If this state is already visited if ((u[0], u[1]) in m): continue # Doesn't met jug constraints if ((u[0] > a or u[1] > b or u[0] < 0 or u[1] < 0)): continue # Filling the vector for constructing # the solution path path.append([u[0], u[1]]) # Marking current state as visited m[(u[0], u[1])] = 1 # If we reach solution state, put ans=1 if (u[0] == target or u[1] == target): isSolvable = True if (u[0] == target): if (u[1] != 0): # Fill final state path.append([u[0], 0]) else: if (u[0] != 0): # Fill final state path.append([0, u[1]]) # Print the solution path sz = len(path) for i in range(sz): print("(", path[i][0], ",", path[i][1], ")") break # If we have not reached final state # then, start developing intermediate # states to reach solution state q.append([u[0], b]) # Fill Jug2 q.append([a, u[1]]) # Fill Jug1 for ap in range(max(a, b) + 1): # Pour amount ap from Jug2 to Jug1 c = u[0] + ap d = u[1] - ap # Check if this state is possible or not if (c == a or (d == 0 and d >= 0)): q.append([c, d]) # Pour amount ap from Jug 1 to Jug2 c = u[0] - ap d = u[1] + ap # Check if this state is possible or not if ((c == 0 and c >= 0) or d == b): q.append([c, d]) # Empty Jug2 q.append([a, 0]) # Empty Jug1 q.append([0, b]) # No, solution exists if ans=0 if (not isSolvable): print ("No solution") # Driver code if __name__ == '__main__': Jug1, Jug2, target = 4, 3, 2 print("Path from initial state " "to solution state ::") BFS(Jug1, Jug2, target) # This code is contributed by mohit kumar 29
C#
using System; using System.Collections.Generic; class GFG{ static 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 Dictionary<Tuple<int, int>, int> m = new Dictionary<Tuple<int, int> ,int>(); bool isSolvable = false; List<Tuple<int, int>> path = new List<Tuple<int, int>>(); // Queue to maintain states List<Tuple<int, int>> q = new List<Tuple<int, int>>(); // Initializing with initial state q.Add(new Tuple<int,int>(0, 0)); while (q.Count > 0) { // Current state Tuple<int, int> u = q[0]; // Pop off used state q.RemoveAt(0); // If this state is already visited if (m.ContainsKey(u) && m[u] == 1) continue; // Doesn't met jug constraints if ((u.Item1 > a || u.Item2 > b || u.Item1 < 0 || u.Item2 < 0)) continue; // Filling the vector for constructing // the solution path path.Add(u); // Marking current state as visited m[u] = 1; // If we reach solution state, put ans=1 if (u.Item1 == target || u.Item2 == target) { isSolvable = true; if (u.Item1 == target) { if (u.Item2 != 0) // Fill final state path.Add(new Tuple<int, int>(u.Item1, 0)); } else { if (u.Item1 != 0) // Fill final state path.Add(new Tuple<int, int>(0, u.Item2)); } // Print the solution path int sz = path.Count; for(int i = 0; i < sz; i++) Console.WriteLine("(" + path[i].Item1 + ", " + path[i].Item2 + ")"); break; } // If we have not reached final state // then, start developing intermediate // states to reach solution state // Fill Jug2 q.Add(new Tuple<int, int>(u.Item1, b)); // Fill Jug1 q.Add(new Tuple<int, int>(a, u.Item2)); for(int ap = 0; ap <= Math.Max(a, b); ap++) { // Pour amount ap from Jug2 to Jug1 int c = u.Item1 + ap; int d = u.Item2 - ap; // Check if this state is possible or not if (c == a || (d == 0 && d >= 0)) q.Add(new Tuple<int, int>(c, d)); // Pour amount ap from Jug 1 to Jug2 c = u.Item1 - ap; d = u.Item2 + ap; // Check if this state is possible or not if ((c == 0 && c >= 0) || d == b) q.Add(new Tuple<int, int>(c, d)); } // Empty Jug2 q.Add(new Tuple<int, int>(a, 0)); // Empty Jug1 q.Add(new Tuple<int, int>(0, b)); } // No, solution exists if ans=0 if (!isSolvable) Console.WriteLine("No solution"); } // Driver code static void Main() { int Jug1 = 4, Jug2 = 3, target = 2; Console.WriteLine("Path from initial state " + "to solution state ::"); BFS(Jug1, Jug2, target); } } // This code is contributed by divyeshrabadiya07
Javascript
<script> function BFS(a,b,target) { // This 2d array is used as a hashmap // to keep track of already visited // values and avoid repetition let m = new Array(1000); for(let i=0;i<1000;i++){ m[i]=new Array(1000); for(let j=0;j<1000;j++) { m[i][j]=-1; } } let isSolvable = false; let path = []; let q = []; // queue to maintain states q.push([0,0]); // Initialing with initial state while (q.length!=0) { let u = q[0]; // current state q.shift(); // pop off used state // doesn't met jug constraints if ((u[0] > a || u[1] > b || u[0] < 0 || u[1] < 0)) continue; // if this state is already visited if (m[u[0]][u[1]] > -1) continue; // filling the vector for constructing // the solution path path.push([u[0],u[1]]); // marking current state as visited m[u[0]][u[1]] = 1; // System.out.println(m.get(new Pair(u.first, u.second))); // if we reach solution state, put ans=1 if (u[0] == target || u[1] == target) { isSolvable = true; if (u[0] == target) { if (u[1] != 0) // fill final state path.push([u[0],0]); } else { if (u[0] != 0) // fill final state path.push([0,u[1]]); } // print the solution path let sz = path.length; for (let i = 0; i < sz; i++) document.write("(" + path[i][0] + ", " + path[i][1] + ")<br>"); break; } // if we have not reached final state // then, start developing intermediate // states to reach solution state q.push([u[0],b]); // fill Jug2 q.push([a,u[1]]); // fill Jug1 for (let ap = 0; ap <= Math.max(a, b); ap++) { // pour amount ap from Jug2 to Jug1 let c = u[0] + ap; let d = u[1] - 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[0] - ap; d = u[1] + 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) document.write("No solution"); } // Driver code let Jug1 = 4, Jug2 = 3, target = 2; document.write("Path from initial state " + "to solution state ::<br>"); BFS(Jug1, Jug2, target); // This code is contributed by unknown2108 </script>
Path of states of jugs followed is : 0 , 0 0 , 3 3 , 0 3 , 3 4 , 2 0 , 2
Complejidad temporal: O(n*m).
Complejidad espacial: O(n*m) . Donde n y m son la cantidad de jug1 y jug2 respectivamente. Este artículo ha sido mejorado por Sparsh Sharma .
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA