자바에서 미로의 다른 솔루션을 어떻게 찾을 수 있습니까?
Nov 15 2020
주어진 txt 파일에서 미로를 취하고 콘솔에 솔루션 경로를 인쇄하는 프로그램을 작성해야합니다. 아래에서 볼 수 있듯이이 프로그램을 작성했지만 해결책은 하나만 찾을 수 있습니다. 미로에 둘 이상의 해결책이 있다면이 모든 것을 찾아야합니다. 나는 이것을 위해 어떤 접근 방식을 취해야할지 모르겠습니다. 아이디어를 주시겠습니까?
내 작품은 다음과 같습니다.
maze.txt (인수로 전송 됨)
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:\n");
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("\nCreated Maze: \n");
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("\nSolution: \n");
//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("\n\n");
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 클래스 :
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
답변
rabbit Nov 16 2020 at 08:11
원하는 결과는 '(동북, 북서)에서 (남동, 남서)까지 갈 수있는 다양한 해법'인데, 스택을 이용해서 풀어야하나요? 그렇다면 두 개의 스택을 사용하는 것이 좋습니다. 하나는 모든 가능성 (모든 toEast, toWest 등을 저장할 수있는 곳에 저장)을 저장하고, 하나는 현재 진행중인 항목 (각 가능한 솔루션을 버퍼로 저장)을 저장합니다.
현재 프로세스를 버퍼에 저장하는 로직을 추가하고 원본 코드에 대한 솔루션 일 때 경로를 인쇄하십시오. 솔루션이 아니고 (남동, 남서)에 도달 할 수없는 경우 버퍼 스택을 추적하고 복원하십시오. 이 논리의 경우 다양한 방향에서 마지막으로 선택한 또 다른 스택 저장 위치가 필요합니다.
요컨대
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.