如何在 java 中找到迷宫的其他解决方案?
我需要编写一个程序，在给定的 txt 文件中获取迷宫并将解决方案路径打印到控制台.我编写了这个程序，如下所示，但我只能找到 1 个解决方案.如果迷宫中有超过 1 个解决方案，我需要找到所有这些.我不知道我应该采取什么方法.请给个思路好吗?
I need to write a program that takes the maze in the given txt file and prints the solution paths to the console. I wrote this program as you can see below, but I can only find 1 solution. If there are more than 1 solution in the maze, I need to find all these. I have no idea what approach I should take for this. Can you give an idea, please?
这是我的工作:
maze.txt(作为参数发送)
maze.txt (sent as argument)
11111111111111111
10110011000111111
11001110111001111
10110001011100111
11101111011011001
11101001011011111
11011011011001011
10111100111110111
11011011011111101
11100111011000011
10011110100111101
10100110111111101
11111111111111111
驱动类:
import java.io.*;
import java.util.Arrays;
public class Driver {
public static void main(String[] args) {
//Reading source file
int rowNum = 0, colNum = 0;
File mazeFile = new File(args[0]);
try (BufferedReader br = new BufferedReader(new FileReader(mazeFile))) {
System.out.println("Input of Readed File:
");
String line;
while ((line = br.readLine()) != null) {
colNum = line.length();
rowNum++;
System.out.println(line);
}
} catch (IOException e) {
e.printStackTrace();
}
//creating new maze array
char[][] maze = new char[rowNum][colNum];
System.out.println();
System.out.print("ROW: "+rowNum+" COL: "+colNum);
//Setting maze's elements
try (BufferedReader br = new BufferedReader(new FileReader(mazeFile))) {
int readed,rNum=0,cNum=0;
while ((readed = br.read()) != -1) {
if(readed == 10){
}
else if(rNum<rowNum && cNum < colNum){
maze[rNum][cNum] = (char)readed;
cNum++;
}
else if(cNum >= colNum){
rNum++;
cNum=0;
}
}
} catch (IOException e) {
e.printStackTrace();
}
//Printing created maze...
System.out.println("
Created Maze:
");
for (int i = 0; i<rowNum ; i++) {
for (int j = 0; j < colNum; j++) {
System.out.print(maze[i][j]);
}
System.out.println();
}
System.out.println("
Solution:
");
//Creating myStack object for making stack operations
Stack myStack = new Stack(1000);
//Creating mazeSolver object for solving maze
MazeSolver mazeSolver = new MazeSolver(myStack,maze,1,1,colNum-2,rowNum-2,rowNum,colNum);
mazeSolver.solve();
//Printing inside of our stack.
//myStack.showElements();
//Creating answer array
char[][] answer = maze;
//Our path is drawn by re-reading the stored data in our stack structure.
for (int i = rowNum-1; i >=0; i--) {
for (int j = colNum-1; j >=0; j--) {
int x[] = myStack.peek();
if(i == x[0] && j == x[1]){
answer[i][j] = '#';
}
}
}
//Minor visual improvements ...
for (int i = 0; i<rowNum ; i++) {
for (int j = 0; j < colNum; j++) {
if(answer[i][j] == '1' || answer[i][j] == '0')
answer[i][j] = '.';
}
}
//Printing our answer
for (int i = 0; i<rowNum ; i++) {
for (int j = 0; j < colNum; j++) {
System.out.print(maze[i][j]);
}
System.out.println();
}
}
}
堆栈类:
public class Stack {
int topOfStack;
int capacity;
int[][] Stack;
public Stack(int capacity) {
this.capacity = capacity;
Stack = new int[capacity][2];
topOfStack = -1;
}
void push(int y, int x)
{
if(topOfStack == capacity){
System.out.println("Stack Overflow...");
}
else{
Stack[++topOfStack] = new int[] { y, x };
}
//System.out.println("###Pushed Element: "+Stack[topOfStack][0]+" "+Stack[topOfStack][1]);
}
int[] pop() {
if (topOfStack < 0) {
System.out.println("Stack is empty...");
return null;
}
//System.out.println("Pulled Element: "+Stack[topOfStack][0]+" "+Stack[topOfStack][1]);
topOfStack--;
return Stack[topOfStack];
}
int[] pop2() {
if (topOfStack < 0) {
System.out.println("Stack Underflow");
return null;
}
else {
int x[] = Stack[topOfStack--];
//System.out.println("Pulled Element: "+x[0]+" "+x[1]);
return x;
}
}
int[] peek()
{
if (topOfStack < 0) {
System.out.println("Stack Underflow");
return null;
}
else {
int x[] = Stack[topOfStack];
return x;
}
}
void showElements()
{
System.out.println("
");
for (int i = topOfStack; i >=0; i--) {
System.out.println("Stack Elements "+i+":"+" "+Stack[i][0] +" "+Stack[i][1]);
}
}
int size(){
int i;
for (i = 0; i <= topOfStack; i++) {
}
return i;
}
}
MazeSolver 类:
MazeSolver Class:
public class MazeSolver {
Stack workStack;
char[][] maze;
int startPointX;
int startPointY;
int endPointX;
int endPointY;
int numberOfRows;
int numberOfCols;
static final char Wall = '1';
static final char Free = '0';
static final char Success = '#';
public MazeSolver(Stack workStack, char[][] maze,int startingPointX, int startingPointY, int endPointX, int endPointY, int RowNum, int ColNum) {
this.workStack = workStack;
this.maze = maze;
this.startPointX = startingPointX;
this.startPointY = startingPointY;
this.endPointX = endPointX;
this.endPointY = endPointY;
this.numberOfRows = RowNum;
this.numberOfCols = ColNum;
workStack.push(startPointY,startingPointX);
}
boolean canMoveEast(){
if((maze[startPointY][startPointX + 1] == Free) && (startPointX + 1 <= numberOfCols))
{
return true;
}
else
return false;
}
boolean canMoveWest(){
if((maze[startPointY][startPointX - 1] == Free) && (startPointX - 1 <= numberOfCols)){
return true;
}
else
return false;
}
boolean canMoveNorth(){
if((maze[startPointY-1][startPointX] == Free) && (startPointY - 1 <= numberOfRows)){
return true;
}
else
return false;
}
boolean canMoveSouth(){
if((maze[startPointY+1][startPointX] == Free) && (startPointY + 1 <= numberOfRows)){
return true;
}
else
return false;
}
boolean canMoveNorthEast(){
if((maze[startPointY-1][startPointX+1] == Free) && (startPointY - 1 <= numberOfRows) && (startPointX + 1 <= numberOfCols)){
return true;
}
else
return false;
}
boolean canMoveNorthWest(){
if((maze[startPointY-1][startPointX-1] == Free) && (startPointY - 1 <= numberOfRows) && (startPointX - 1 <= numberOfCols)){
return true;
}
else
return false;
}
boolean canMoveSouthEast(){
if((maze[startPointY+1][startPointX+1] == Free) && (startPointY + 1 <= numberOfRows) && (startPointX + 1 <= numberOfCols)){
return true;
}
else
return false;
}
boolean canMoveSouthWest(){
if((maze[startPointY+1][startPointX-1] == Free) && (startPointY + 1 <= numberOfRows) && (startPointX - 1 <= numberOfCols)){
return true;
}
else
return false;
}
boolean solve()
{
maze[startPointY][startPointX] = Success;
//Checked if we reached our goal
if((startPointY == endPointY) && (startPointX == endPointX)){
return true;
}
if(canMoveEast()){
workStack.push(startPointY,startPointX+1);
startPointX++;
solve();
}
else if(canMoveWest()){
workStack.push(startPointY,startPointX-1);
startPointX--;
solve();
}
else if(canMoveNorth()){
workStack.push(startPointY-1,startPointX);
startPointY--;
solve();
}
else if(canMoveSouth()){
workStack.push(startPointY+1,startPointX);
startPointY++;
solve();
}
else if(canMoveNorthEast()){
workStack.push(startPointY-1,startPointX+1);
startPointY--;
startPointX++;
solve();
}
else if(canMoveNorthWest()){
workStack.push(startPointY-1,startPointX-1);
startPointY--;
startPointX--;
solve();
}
else if(canMoveSouthEast()){
workStack.push(startPointY+1,startPointX+1);
startPointY++;
startPointX++;
solve();
}
else if(canMoveSouthWest()){
workStack.push(startPointY+1,startPointX-1);
startPointY++;
startPointX--;
solve();
}
else if(true){
try {
maze[startPointY][startPointX] = Wall;
int[] back = workStack.pop();
startPointY = back[0];
startPointX = back[1];
solve();
} catch (Exception e) {
System.out.println("There is no solution!");
System.exit(0);
}
}
return false;
}
}
我得到的输出:
Input of Readed File:
11111111111111111
10110011000111111
11001110111001111
10110001011100111
11101111011011001
11101001011011111
11011011011001011
10111100111110111
11011011011111101
11100111011000011
10011110100111101
10100110111111101
11111111111111111
ROW: 13 COL: 17
Created Maze:
11111111111111111
10110011000111111
11001110111001111
10110001011100111
11101111011011001
11101001011011111
11011011011001011
10111100111110111
11011011011111101
11100111011000011
10011110100111101
10100110111111101
11111111111111111
Solution:
.................
.#...............
..##...#.........
....###.#........
........#........
........#........
........#........
.......#.........
........#........
........#..####..
.........##....#.
...............#.
.................
Process finished with exit code 0
我需要的输出:
Input of Readed File:
11111111111111111
10110011000111111
11001110111001111
10110001011100111
11101111011011001
11101001011011111
11011011011001011
10111100111110111
11011011011111101
11100111011000011
10011110100111101
10100110111111101
11111111111111111
ROW: 13 COL: 17
Created Maze:
11111111111111111
10110011000111111
11001110111001111
10110001011100111
11101111011011001
11101001011011111
11011011011001011
10111100111110111
11011011011111101
11100111011000011
10011110100111101
10100110111111101
11111111111111111
Solution 1:
.................
.#...............
..##...#.........
....###.#........
........#........
........#........
........#........
.......#.........
........#........
........#..####..
.........##....#.
...............#.
.................
Solution 2:
.................
.#...............
..##.............
....#............
...#.............
...#.............
..#..............
.#....##.........
..#..#..#........
...##...#..####..
.........##....#.
...............#.
.................
Process finished with exit code 0
推荐答案
你想要的结果是'多种解决方案可以通过(Northeast, Northwest) to (Southeast, Southwest)'，你需要解决使用堆?如果是这样，我建议您使用两个堆栈，一个用于保存所有可能性(存储所有 toEast、toWest 等您可以去的地方)，一个用于保存当前正在进行的(每个可能的解决方案，作为缓冲区)
The result you want is 'A variety of solutions which can go through (Northeast, Northwest) to (Southeast, Southwest)', and you need to solve using stack? If so, I suggest you to use two stack, one for saving all possibilities(which store all toEast, toWest etc where you can go), one for saving current ongoings(each possible solutions, as a buffer)
只需添加将当前进程保存在缓冲区中的逻辑，并在它是原始代码的解决方案时打印路径.如果它不是解决方案并且无法到达(东南，西南)，则回溯并恢复您的缓冲区堆栈.对于这个逻辑，您需要另一个堆栈保存位置，您上次从各种方向选择的位置.
Just add logic that saves current process in buffer, and print path when it Is a solution on your original code. If it's not a solution and cannot reach (Southeast, Southwest), traceback and restore your buffer stack. For this logic, you'll need another stack saving location where you last picked on from varieties of directions.
总之，
Stack1 => to save all possibilities
Stack2 => current paths. If not a solution, delete and restore
Stack3 => where you chose one direction from many. Need to traceback the path.
Stack2 copies Stack1 whenever you progress,
when reach the goal you print your Stack2 as a solution,
if not, pop until your latest decision informed by popping Stack3.
相关文章