Bewegen durch das Labyrinth

[javaHK]

hi,

habe mich mal an die zweite Aufgabe des Informatikwettbewerbs herangewagt, doch bin jetzt auf Probleme
gestoschen beim Durchgehen des Labyrinths.




Hier mein Code

public class Ludwig {
	static int goon =0;
	static int ziel = 14;
	static Point mp = new Point (3,3);
	
	
	
	
	
		
		public static BitSet wände (int k)   // Methode damit man die Wände erkennen kann. Wenn z.B. der Wert
                                                                       7 übergeben wird, dann werden die ersten drei Bits auf true gesetzt.
                                                                          2 hoch 0 + 2 hoch 1 + 2 hoch2 = 7
                                                                           linke Wandseite = 3
                                                                           Obere Wandseite = 2
                                                                           Untere Wandseite =1
                                                                           rechte Wandseite =0
                                                                            Wenn dann jetzt in diesem zweidimensionalen Array die 7 auftaucht, weiß ich das links, recht und unten eine Wand ist.
                                                                                     

			{
		
				BitSet bs = new BitSet();
				int numb =0;
				for (int i=4;i>=0;i--)
				{
			
			
					if (Math.pow(2,i)<= (k-numb))
					{
						bs.set( i);
						numb = (int) (numb+Math.pow(2,i));
				
					}
					if (numb==k)
					break;
			
			
				}
		
		
				System.out.println (bs);
		
		
		
				return bs;
		
			}
	
	public static void main (String args [])
	{
		
		 int Feldyx [][] = { {12,6,5,13},           //Habe erst einmal ein kleineres Labyrinth genommen. 
						  {8,5,9,9},
						  {9,11,8,1},
						  {11,14,3,11}
						  
		};
		
		int Startpos = 11; 
		Point p [] = new Point [16];
		
		
		
		
		
		
		for (int i =0;i<4;i++) Hier wird ermittelt, wo die Startposition liegt, aber noch nicht festgelegt um welche 11 es sich genau handelt.
		{
			for (int x=0; x<4;x++)
			{
				if (Feldyx[i][x]== Startpos)
				{
					p[goon] = new Point (x,i);
					
					System.out.println(p[goon]); 
					goon++;
				}
				
				
			}
			
		
		}
		//wände(3);
		
		
		BitSet wand = new BitSet();
		wand = wände (14); // In der Var befinden sich die Wände für die Zahl in Klammern 
		
		//if (!wand.get( ))
			
		do
		{
		

		
		}while (mp.x==2 && mp.y ==1); Ziel, hier steht das Futter der Maus, also an diesen Koordinaten
		
		
		
		
		
		
		
		
		
		
		
		
		}


}

Wie kann ich mich jetzt durch das Labyrinth bewegen? Also wie kann ich einen Schritt vorwärts machen dann die Wände überprüfen und dann nach z.B. links gehen? Kann ich das mit dem Point Objekt machen, also das dieses immer verschoben wird?

Welche Suchstrategie könnte ich anwenden um durch das Labyrinth zu kommen?

http://www.bwinf.de/aufgaben/runde1/bwi201/html/aufgabe_2.html Der Link der Aufgabenstellung

[Edit by Beni: URL reparriert]

 

[Guest]

Wie kann ich mich durch das Labyrinth bewegen, welche Suchstrategie muss ich benutzen?

 

[Guest]

Rekursion.

- Du gehst bei jedem Rekursionsschritt ein Feld weiter. Immer, wo es gerade geht und wo Du bisher nicht warst.
(links, vor, rechts)
- Reihenfolge immer einheitlich. Richtung ändert sich nach dem Abbiegen
- Du merkst Dir jede Position, die Du besucht hast
- Betritts Du die gleiche Stelle erneut, gest Du einen Schritt zurück (Rekursionsschritt zurück)

Das ganze solange Du nicht wieder im Ursprung landest oder das Ziel gefunden hast.

Alternative: GPS oder Geruchssensor.

 

[Guest]

So ungefähr sollte es gehen

Position schritt(Position pos, int richtung)
{
  // Da war ich schon, raus hier
  if(warSchonHier(pos))
    return null;
  // Aktuelle Position als besucht markieren
  setWarSchonHier(pos);

  // Käse gefunden?
  Position gefunden = kaeseDa(pos);

  // Nach links
  if(gefunden!=null && gehtEsLinks(pos, richtung))
    gefunden = schritt(nachLinks(pos, richtung), nachLinks(richtung));

  // Vor
  if(gefunden!=null && gehtEsVorwaerts(pos, richtung))
    gefunden = schritt(vorwarts(pos), richtung);

  // Nach rechts
  if(gefunden!=null && gehtEsRechts(pos, richtung))
    gefunden = schritt(nachRechts(pos, richtung), nachRechts(richtung));

// Den Wegpunkt ausgeben
  if(gefunden!=null)
    ausgabe(pos); 

  return gefunden;
}

Der Weg zum Käse wird dabei Rückwärts ausgegeben.

 

[Guest]

Ehmm bei 'links', 'vor' und 'rechts' jeweils

if(gefunden==null &&

 

[Guest]

Danke, aber was muss ich bei "warschohier" für eine Methode schreiben oder nach "esgehtlinks" ?

 

[Guest]

public class Ludwig {
	static int goon =0;
	static int ziel = 14;
	static Point mp = new Point (3,3);
	static int Feldyx [][] = { {12,6,5,13},
	{8,5,9,9},
	{9,11,8,1},
	{11,14,3,11}};
	
	
	
	/*public static BitSet wände (int wert)
		{
			BitSet bs = new BitSet ();
			int pos =7;
			/*if (pos<=8)
			{
				bs.set (1);
				pos = pos-8;
			}
			else
			bs.set (0);
		
		
			int arr [] = {8,4,2,1};
			int on=0;
			for (int i =0;i<4;i++)
			{
				if (pos >=arr[on])
				{
					bs.set( i);
					pos = pos-arr[on];
					System.out.println (1);
					on++;
				}
				else
				{
			
				bs.set( i);
				System.out.println (0);
				on++;
				}
			}
		
		
		System.out.println (bs);
		
		
		
		
		
			return bs;
		
		}*/
		
		public static BitSet wände (int k)
			{
		
				BitSet bs = new BitSet();
				int numb =0;
				for (int i=4;i>=0;i--)
				{
			
			
					if (Math.pow(2,i)<= (k-numb))
					{
						bs.set( i);
						numb = (int) (numb+Math.pow(2,i));
				
					}
					if (numb==k)
					break;
			
			
				}
		
		
				System.out.println (bs);
		
		
		
				return bs;
		
			}
	
	public static void main (String args [])
	{
		
		 int Feldyx [][] = { {12,6,5,13},
						  {8,5,9,9},
						  {9,11,8,1},
						  {11,14,3,11}
						  
		};
		
		int Startpos = 11;
		Point p [] = new Point [16];
		
		/*for (int i =0;i<4;i++)
		{
			if (Feldyx[i][0] == Startpos)
				//p[0] = new Point (0,i);
			
			System.out.println (p);
					
		}*/
		
		
		
		
		for (int i =0;i<4;i++)
		{
			for (int x=0; x<4;x++)
			{
				if (Feldyx[i][x]== Startpos)
				{
					p[goon] = new Point (x,i);
					
					System.out.println(p[goon]); 
					goon++;
				}
				
				
			}
			
		
		}
		//wände(3);
		
		
		BitSet wand = new BitSet();
		//wand = wände (14); // In der Var befinden sich die Wände für die Zahl in Kla. 
		
		//if (!wand.get( ))
			
		/*do
		{
			int twand = Feldyx [1][1];
		
			if ( !wand.get(2))
				{
					mp.x--;
					mp.y = 2;
					System.out.println ("Maus" + mp);
				}
		Wert_für_Labyrinthkoordinate (mp.y, mp.x);
		System.out.println ("e"+twand);
		
		
		}while (mp.x==2 && mp.y ==1);*/
		int xL = 3;
		int yL = 3;
		
		do
		{
			
			
			wand = wände (Feldyx [yL][xL]);
			
			if (!wand.get( 2))
			{
				System.out.println ("Nord");
				yL--;		
			}
			
			
			
		}while (true);
		
		
		
		
		
		
		
		
		}


		public static int Wert_für_Labyrinthkoordinate (int Koy, int Kox)
		{
			
			int returnK = Feldyx [Koy] [Kox];
			
			
			System.out.println ("kor"+returnK);
			
			
			
			
			
			return returnK;
			
		}
}

 

[Guest]

Danke, aber was muss ich bei "warschohier" für eine Methode schreiben oder nach "esgehtlinks" ?

Mit warSchonHier(pos) prüfst Du, ob Du an der gegebenen Position bereits warst.
Wenn nicht, dann markierst Du diese Position als 'besucht' und gehst solange zurück,
bis eine der früheren Positionen einen aternativen Gang anbietet.

Mit gehtEsNachLinks() etc. stellst Du fest, ob man, ausgehend von der aktuellen Position,
nach links/rechts/vorne gehen kann oder ist da 'ne Wand.

Das läuft alles rekursiv, so dass Du Dich nur um die Bedingungen für's abbiegen und
die Ermittlung besuchter Punkte kümmern mußt. Ehmm und ob Käse da ist.

Ist ja einfach wie Fi...

So wie ich das verstanden habe, sind diese Aufgaben alleine zu erledigen, daher kann
Dir hier jeder nur einen Tip geben, nicht aber die komplette Lösung.
Die Aufgaben finde ich aber etwas heavy für die genannte Zielgruppe. Da wird sicherlich
geschummelt, was das Zeug hält. Wenn Euch irgendwelche gestressten IT-Papas, nach
Käse-Such-Algorithmen fragen, dann wisst Ihr Bescheid :bae: