fork(14) download
copy 
  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4. import java.util.Queue;
  5. import java.util.Stack;
  6. import java.util.Iterator;
  7.  
  8. class Jarras {
  9.  
  10.  
  11. 	int j4, j3;
  12. 	List<Jarras> hijos;
  13. 	int nodosAnalizados, largoBusqueda;
  14.  
  15. 	public Jarras(int j4, int j3)
  16. 	{
  17. 		this.j4 = j4;
  18. 		this.j3 = j3;
  19. 		hijos = new ArrayList<Jarras>();
  20. 	}
  21.  
  22.    public void addHijos(Jarras hijo)
  23.    {
  24.    	hijos.add(hijo);
  25.    }
  26.  
  27.  
  28.     public void Estados()
  29.     {
  30.     	int ij4;
  31.     	int ij3;
  32.  
  33.     	for (int operador = 0; operador < 6;operador++)
  34.     	{
  35.  
  36.  
  37.  
  38.                        //llenar garrafa de 4L
  39.                         if (operador == 0 && this.j4<4 ){
  40.                                 ij4 = 4;
  41.                                 ij3 = this.j3;
  42.                                 Jarras nodo = new Jarras(ij4,ij3);
  43.                                 hijos.add(nodo);
  44.                         } 
  45.  
  46.                         //llenar garrafa de 3L
  47.                         if (operador == 1 && this.j3<3 ){
  48.                         	 	ij4 = this.j4;
  49.                                 ij3 = 3;   
  50.                                 Jarras nodo = new Jarras(ij4,ij3);
  51.                                 hijos.add(nodo);
  52.                         }
  53.  
  54.                         //vaciar garrafa de 4L
  55.                         if (operador == 2 && this.j4>0 ){
  56.                                 ij4 = 0;
  57.                                 ij3 = this.j3;
  58.                                 Jarras nodo = new Jarras(ij4,ij3);
  59.                                 hijos.add(nodo);
  60.                         }
  61.                         //vaciar garrafa de 3L
  62.                         if (operador == 3 && this.j3>0 ){
  63.                                 ij4 = this.j4;
  64.                                 ij3 = 0;
  65.                                 Jarras nodo = new Jarras(ij4,ij3);
  66.                                 hijos.add(nodo);
  67.                         }
  68.                         //verter garrafa de 3L sobre garrafa de 4L
  69.                         if (operador == 4 && this.j3>0 && this.j4<4 ){
  70.                                 if (this.j3+this.j4 <= 4){
  71.                                         ij4=this.j3+this.j4;
  72.                                         ij3=0;
  73.                                         Jarras nodo = new Jarras(ij4,ij3);
  74.                                			 hijos.add(nodo);
  75.                                 }
  76.                                 else {
  77.                                         ij4 = 4;
  78.                                         ij3 = (this.j3+this.j4)-4;
  79.                                         Jarras nodo = new Jarras(ij4,ij3);
  80.                                			 hijos.add(nodo);
  81.                                 }
  82.  
  83.                         }
  84.                         //verter garrafa de 4L sobre garrafa de 3L
  85.                         if (operador == 5 && this.j4>0 && this.j3<3 ){
  86.                                 if (this.j3+this.j4 <= 3){
  87.                                         ij3=this.j3+this.j4;
  88.                                         ij4=0;
  89.                                         Jarras nodo = new Jarras(ij4,ij3);
  90.                                			 hijos.add(nodo);
  91.                                 }
  92.                                 else {
  93.                                         ij3 = 3;
  94.                                         ij4 = this.j4-(3-this.j3);
  95.                                         Jarras nodo = new Jarras(ij4,ij3);
  96.                                			 hijos.add(nodo);
  97.                                 }
  98.  
  99.                         }
  100.     	}
  101.  
  102.     }
  103.  
  104.  
  105.     public String getEstado()
  106.     {
  107.     	return "("+j4+","+j3+")";
  108.     }
  109.  
  110.  
  111.      public List<Jarras> getHijos() {
  112.  
  113.  
  114.         return hijos;
  115.  
  116.  
  117.     }
  118.  
  119.     public int getNodosAnalizados()
  120.     {
  121.     	return nodosAnalizados;
  122.     }
  123.  
  124.     public int getLargoBusqueda()
  125.     {
  126.     	return largoBusqueda;
  127.     }
  128.  
  129.  
  130.  
  131.  
  132.  
  133. 	public boolean busquedaAnchura() {
  134.  
  135.  
  136. 	    List<Jarras> recorridos = new ArrayList<Jarras>();
  137.         Queue<Jarras> colaAuxiliar = new LinkedList<Jarras>();
  138.         colaAuxiliar.add(this);
  139. 		Iterator<Jarras> nombreIterator;
  140. 		boolean estado;
  141. 		nodosAnalizados = 0;
  142. 		largoBusqueda = 0;
  143.  
  144.  
  145.         while(colaAuxiliar.size() != 0) 
  146.         {
  147.  
  148.             Jarras cabeza = colaAuxiliar.poll();
  149. 			estado = true;
  150. 			nombreIterator = recorridos.iterator();
  151.  
  152. 			while(nombreIterator.hasNext())
  153. 			{
  154. 				Jarras compar = nombreIterator.next();
  155.  
  156. 				if((cabeza.j4 == compar.j4) && (cabeza.j3 == compar.j3))
  157. 				{
  158. 					estado = false;
  159. 					break;
  160. 				}
  161. 			}
  162.  
  163. 			if(estado == true)
  164. 			{
  165.  
  166.             	System.out.println(cabeza.getEstado() );  // solo añadido como informacion para nosotros
  167. 				recorridos.add(cabeza);
  168. 				nodosAnalizados++;
  169.  
  170.            		 if(cabeza.j4 == 2 )
  171.            		 {
  172.            		     return true;
  173.           	 	 }
  174.  
  175.           		 else
  176.         	    {
  177. 					cabeza.Estados();
  178.              	   for(Jarras hijo : cabeza.getHijos())
  179.              	   {
  180.              	   	largoBusqueda++;
  181.                	     colaAuxiliar.add(hijo);
  182.              	   }                   
  183.           	    }	
  184. 		   }			
  185.         }
  186.  
  187.         return false;
  188.  
  189.  
  190.     }
  191.  
  192.  
  193.  
  194.    	public boolean busquedaProfundidad() {
  195.  
  196.  
  197. 	    List<Jarras> recorridos = new ArrayList<Jarras>();
  198.         Stack<Jarras> pilaAuxiliar = new Stack<Jarras>();
  199.         pilaAuxiliar.push(this);
  200. 		Iterator<Jarras> nombreIterator;
  201. 		boolean estado;
  202. 		nodosAnalizados = 0;
  203. 		largoBusqueda = 0;
  204.  
  205.         while(pilaAuxiliar.size() != 0) 
  206.         {
  207.  
  208.             Jarras cabeza = pilaAuxiliar.pop();
  209. 			estado = true;
  210. 			nombreIterator = recorridos.iterator();
  211.  
  212. 			while(nombreIterator.hasNext())
  213. 			{
  214. 				Jarras compar = nombreIterator.next();
  215.  
  216. 				if((cabeza.j4 == compar.j4) && (cabeza.j3 == compar.j3))
  217. 				{
  218. 					estado = false;
  219. 					break;
  220. 				}
  221. 			}
  222.  
  223. 			if(estado == true)
  224. 			{
  225.  
  226.             	System.out.println(cabeza.getEstado() );  // solo añadido como informacion para nosotros
  227. 				recorridos.add(cabeza);
  228. 				nodosAnalizados++;
  229.  
  230.            		 if(cabeza.j4 == 2 )
  231.            		 {
  232.            		     return true;
  233.           	 	 }
  234.  
  235.           		 else
  236.         	    {
  237.  
  238. 					cabeza.Estados();
  239.  
  240. 					for(int i = 0;i < pilaAuxiliar.size(); i++)
  241. 					{
  242. 						Jarras p = pilaAuxiliar.get(i);
  243. 						for(int j=0; j < cabeza.getHijos().size();j++)
  244. 						{
  245. 							Jarras p2 = cabeza.getHijos().get(j);
  246. 							if((p2.j4 == p.j4) && (p2.j3 == p.j3))
  247. 							{
  248. 								cabeza.hijos.remove(j);
  249. 							}
  250. 						}
  251.  
  252. 					}		
  253.              	   		for(int i = cabeza.getHijos().size() -1; i >= 0;i--)
  254.              	   		{
  255.              	   			largoBusqueda++;
  256.                	     		pilaAuxiliar.push(cabeza.getHijos().get(i));
  257.              	   		} 
  258. 					}                  
  259.           	    }	
  260. 		   }
  261. 		    return false;			
  262.         }
  263.  
  264.  
  265.  
  266.  
  267.     }
  268.  
  269.  
  270.  
  271.  
  272.  
  273. class MainJarras
  274. {
  275.  
  276.  
  277. public static void main (String[] args) {
  278.  
  279. 	Jarras inicio = new Jarras(0,0);
  280. 	System.out.println("BUSQUEDA EN ANCHURA");
  281. 	inicio.busquedaAnchura();
  282. 	System.out.println("Nodos Analizados :"+inicio.getNodosAnalizados());
  283. 	System.out.println("Largo Busqueda :"+inicio.getLargoBusqueda());	
  284. 	System.out.println();	
  285. 	System.out.println("BUSQUEDA EN PROFUNDIDAD");
  286. 	inicio.busquedaProfundidad();
  287. 	System.out.println("Nodos Analizados :"+inicio.getNodosAnalizados());
  288. 	System.out.println("Largo Busqueda :"+inicio.getLargoBusqueda());
  289. }
  290.  
  291. }
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
BUSQUEDA EN ANCHURA
(0,0)
(4,0)
(0,3)
(4,3)
(1,3)
(3,0)
(1,0)
(3,3)
(0,1)
(4,2)
(4,1)
(0,2)
(2,3)
Nodos Analizados :13
Largo Busqueda :42

BUSQUEDA EN PROFUNDIDAD
(0,0)
(4,0)
(4,3)
(1,3)
(1,0)
(0,1)
(4,1)
(2,3)
Nodos Analizados :8
Largo Busqueda :19
https://ideone.com/GwKEKt
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!