Ik ben toegewezen met de taak om een doolhofolver in Java te maken. Hier is de opdracht:
Write an application that finds a path through a maze.
The maze should be read from a file. A sample maze is shown below.
O O O O O X O
X X O X O O X
O X O O X X X
X X X O O X O
X X X X O O X
O O O O O O O
X X O X X X O
Het teken ‘X’ staat voor een muur of een geblokkeerde positie en het teken ‘O’ vertegenwoordigt een
open positie. Je kunt aannemen dat de ingang van het doolhof altijd in de rechterbenedenhoek is
hoek, en de uitgang is altijd in de linkerbovenhoek. Uw programma moet zijn
uitvoer naar een bestand. Als een pad wordt gevonden, moet het uitvoerbestand het pad bevatten. Als een pad is
Niet gevonden Een bericht moet naar het bestand worden verzonden. Houd er rekening mee dat een doolhof meer dan heeft
één oplossingspad, maar in deze oefening wordt alleen gevraagd om één oplossing te lokaliseren, niet
alle oplossingen.
Uw programma moet een stapel gebruiken om het pad op te nemen dat het verkent en backtrack is wanneer deze
bereikt een geblokkeerde positie.
Zorg ervoor dat u een compleet algoritme schrijft voordat u uw code schrijft. Voel je vrij om extra te maken
Klassen die u helpen bij het voltooien van de opdracht.
Here's my Algorithm:
1)Initialize array list to hold maze
2)Read text file holding maze in format
o x x x x o
o o x o x x
o o o o o x
x x x x o o
3)Create variables to hold numbers of columns and rows
3)While text file has next line
A. Read next line
B. Tokenize line
C. Create a temporary ArrayList
D. While there are tokens
i. Get token
ii. create a Point
iii. add point to temp ArrayList
iv. increment maximum number of columns
E. Add temp to maze arraylist, increment max rows
F. initialize a hold of points as max rows - 1
G. Create a start point with x values as maximum number of rows - 1, and y values as maximum number of columns - 1
H. Create stack of points and push starting location
I. While finished searching is not done
i. Look at top of stack and check for finish
ii. check neighbors
iii. is there an open neighbor?
- if yes, update flags and push
- if no, pop from stack
J. Print solution
4. Done is true
Hoe dan ook, wat ik heb opgezet is een Points-klasse die set/get-methoden heeft voor reizen in alle windrichtingen die booleans retourneren zoals weergegeven:
public class Points<E>
{
private int xCoord;
private int yCoord;
private char val;
private boolean N;
private boolean S;
private boolean E;
private boolean W;
public Points()
{
xCoord =0;
yCoord =0;
val =' ';
N = true;
S = true;
E = true;
W = true;
}
public Points (int X, int Y)
{
xCoord = X;
yCoord = Y;
}
public void setX(int x)
{
xCoord = x;
}
public void setY(int y)
{
yCoordinate = y;
}
public void setNorth(boolean n)
{
N = n;
}
public void setSouth(boolean s)
{
S= s;
}
public void setEast(boolean e)
{
E = e;
}
public void setWest(boolean w)
{
W = w;
}
public int getX()
{
return xCoord;
}
public int getY()
{
return yCoord;
}
public char getVal()
{
return val;
}
public boolean getNorth()
{
return N;
}
public boolean getSouth()
{
return S;
}
public boolean getEast()
{
return E;
}
public boolean getWest()
{
return W;
}
public String toString1()
{
String result = "(" + xCoord + ", " +yCoord + ")";
return result;
}
}
Ik heb gewoon problemen om de daadwerkelijke oplossing in het algemeen te krijgen. Dit is wat ik heb:
import java.io.*;
import java.util.*;
import java.lang.*;
import java.text.*;
public class MazeSolve1
{
public static void main(String[] args)
{
//Create arrayList of Points
ArrayList<ArrayList<Points>> MAZE = new ArrayList<ArrayList<Points>>();
Scanner in = new Scanner(System.in);
//Read File in
System.out.print("Enter the file name: ");
String fileName = in.nextLine();
fileName = fileName.trim();
FileReader reader = new FileReader(fileName+".txt");
Scanner in2 = new Scanner(reader);
//Write file out
FileWriter writer = new FileWriter("Numbers.out");
PrintWriter out = new PrintWriter(writer);
boolean done = false;
int maxCol = 0;
int maxRow = 0;
while(!done) {
//creating array lists
while (in2.hasNextLine()) {
//Read next line
String nextLine = in2.nextLine();
//Tokenize Line
StringTokenizer st = new StringTokenizer(nextLine, " ");
//Create temp ArrayList
ArrayList<ArrayList<Points>> temp = new ArrayList<ArrayList<Points>>();
//While there are more tokens
while (st.hasNextToken()) {
String token = st.nextToken();
Points pt = new Points();
temp.add(pt);
maxCol++
}
MAZE.add(temp);
maxRow++;
}
//create hold arraylist for max rows of maze -1
//create variables for start x and y coordinates
ArrayList<ArrayList<Points>> hold = new ArrayList<ArrayList<Points>>();
hold = MAZE.get(maxRow - 1);
int startColumn = hold.get(maxCol - 1);
int startRow = hold.get(maxRow - 1);
Point start = new Point();
start.setX(startColumn);
start.setY(startRow);
//initialize stack, and push the start position
MyStack<Points> st = new ArrayStack<Points>();
st.push(start.toString1());
//south and east of start are edges of array
start.setSouth(false);
start.setEast(false);
//while your position is not equal to point (0,0) [finish]
while (st.peek() != "(0, 0)") {
//getting the next coordinate to the North
int nextY = start.getY() - 1;
int nextX = start.getX();
//if character to the North is an O it's open and the North flag is true
if (hold.get(nextY) = 'O' && start.getNorth() == true) {
//set flags and push coordinate
start.setNorth(false);
st.push(start.toString1());
}
//else pop from stack
else { st.pop(); }
//look at coordinate to the East
nextX = start.getX() + 1;
//if character to the East is a O and the East flag is true
if (hold.get(nextX) = 'O' && start.getEast() == true) {
//set flags and push coordinate
start.setEast(false);
st.push(start.toString1());
}
//else pop from stack
else { st.pop(); }
//look at coordinate to the South
nextY = start.getY() + 1;
//if character to the South is a O and the West flag is true
if (hold.get(nextY) = 'O' && start.getSouth() == true) {
//set flags and push coordinate
start.setSouth(false);
st.push(start.toString1());
}
//else pop from stack
else { st.pop() }
//keep looping until the top of the stack reads (0, 0)
}
done = true;
}
//Print the results
System.out.println("---Path taken---");
for (int i = 0; i< st.size(); i++) {
System.out.println(st.pop);
i++
}
Afgezien van eventuele syntaxisfouten, kunnen jullie me wat hulp bieden? Heel erg bedankt.
Antwoord 1, autoriteit 100%
Ik heb hier een soortgelijk antwoord ingediend Maze Solving Algorithm in C++.
Om een kans te hebben om het op te lossen, moet je:
- Maak een
Solve()-routine en roep zichzelf recursief aan:- als 1e, 2e, 3e, … waar is
Solveis erin geslaagd een oplossing te vinden - als 1st, 2nd, 3rd, … een false bevat, moet het teruggaan en een andere manier vinden
- als 1e, 2e, 3e, … waar is
- Je moet een buffer opbouwen van plaatsen waar je bent geweest om oneindige lussen te voorkomen
- als je bewegingen maakt, moet hij het in de gaten houden
- wanneer we op een dood spoor komen, moeten we slechte zetten wissen
- we kunnen het bovenstaande implementeren door een gok in te branden en deze te verwijderen als deze verkeerd is
Hier is wat pseudo-code voor de oplossing.
boolean solve(int X, int Y)
{
if (mazeSolved(X, Y))
{
return true;
}
// Test for (X + 1, Y)
if (canMove(X + 1, Y))
{
placeDude(X + 1, Y);
if (solve(X + 1, Y)) return true;
eraseDude(X + 1, Y);
}
// Repeat Test for (X - 1, Y), (X, Y - 1) and (X, Y + 1)
// ...
// Otherwise force a back track.
return false;
}
Antwoord 2, autoriteit 54%
U zou waarschijnlijk uw programma modulemoeten gebruiken – zoals ik het begrijp, bent u het doolhof aan het lezen uit het bestand en probeer het tegelijkertijd op te lossen.
Een betere aanpak is om het programma in 2 afzonderlijke delen te splitsen:
- lees het invoerbestand en maak een matrix met alle gegevens
- los het doolhof op uit een gegeven matrix
Als je dit doet, kun je elk onderdeel apart bouwen en testen, wat waarschijnlijk zal resulteren in een beter, betrouwbaarder programma.
Het oplossen van het doolhof kan worden gedaan door een eenvoudige BFS, die vergelijkbaar is met wat uw algoritme suggereerde oorspronkelijk , wat een DFS
is
Antwoord 3, autoriteit 8%
Zoals amit al zei, moet je eerst het hele doolhof lezen en opslaan als een tweedimensionale array. Hierdoor kun je het hele doolhof zien zonder het regel voor regel op te lossen.
Omdat je eerst de grootte van de array moet vinden, moet je het tekstbestand in een lijst met strings lezen.
List<String> strs = new ArrayList<String>();
//Pseudocode, choose however you want to read the file
while(file_has_next_line) {
strs.add(get_next_line);
}
De grootte van de lijst geeft je het aantal rijen, en ervan uitgaande dat het altijd een raster is, kun je split().length, (tel spaties + 1) gebruiken of de symbolen op een van de tekenreeksen tellen om de aantal kolommen.
De eenvoudigste manier om de kaartgegevens op te slaan is met een 2D-array met booleans. Waar waar een muur is en onwaar is lege ruimte.
boolean[][] wallMap = new boolean[rows][cols];
for(int i = 0; i < wallMap.length; i++) {
//Separate each symbol in corresponding line
String[] rowSymbols = strs.get(i).split(" ");
for(int j = 0; j < wallMap[i].length; j++) {
//Ternary operator can be used here, I'm just keeping it simple
if(rowSymbols[j].equals("X")) {
wallMap[i][j] = true;
} else {
wallMap[i][j] = false;
}
}
}
Nu je de kaartgegevens in een array hebt opgeslagen, is het veel gemakkelijker om de kaart te doorkruisen en je keuzes te maken. Je kunt ofwel een kant-en-klaar algoritme gebruiken (zie het antwoord van amit) of je eigen algoritme maken. Aangezien dit huiswerk is, moet je proberen je eigen te bedenken.
Veel plezier.
Antwoord 4
Je moet je programma in twee fasen opsplitsen. De eerste is de initialisatie, waar je de doolhofbeschrijving en de beginpositie van de speler leest. Hierna heb je een datastructuur om het bestuur te vertegenwoordigen. De tweede is het eigenlijke spel, waar er 3 abstracties zouden moeten zijn:
- De spelerstatus. In jouw geval is het vrij eenvoudig, de feitelijke positie op het bord.
- Het doolhof zelf, dat is de omgeving. Het zou functies moeten hebben die je vertellen of je een bepaalde positie hebt bezocht, om de positie die je hebt bezocht te markeren, waar het doel is, de volgende bereikbare cellen, enz…
- De logica, dat is het zoekalgoritme.
Elk van deze zou moeten kunnen veranderen zonder veel verandering van de anderen. U kunt bijvoorbeeld worden gevraagd om uw zoekalgoritme te verbeteren, of een probleem waarbij u meer dan één doel heeft. Het gemak van het overschakelen van het huidige probleem naar een licht gewijzigd probleem is de echte maatstaf van een programmaontwerp.
Antwoord 5
Ik heb geprobeerd dit te implementeren met behulp van het DFS-algoritme met behulp van enkele Java OOP-concepten.
Zie volledige oplossing op mijn GitHub Repository
private boolean solveDfs() {
Block block = stack.peekFirst();
if (block == null) {
// stack empty and not reached the finish yet; no solution
return false;
} else if (block.equals(maze.getEnd())) {
// reached finish, exit the program
return true;
} else {
Block next = maze.getNextAisle(block);
// System.out.println("next:" + next);
if (next == null) {
// Dead end, chose alternate path
Block discard = stack.pop();
discard.setInPath(false);
// System.out.println("Popped:" + discard);
} else {
// Traverse next block
next.setVisited(true);
next.setInPath(true);
stack.push(next);
}
}
return solveDfs();
}