m × n 직사각형 어레이는 미로를 나타내고, 0과 1은 각각 미로의 경로와 장애물을 나타냅니다. Maze 설정에서 출구 출구에서 길을 찾기위한 프로그램을 설계하거나 경로가 없다는 결론을 내립니다.
(1) 2 차원 배열에 따라 미로의 그래프를 출력하십시오.
(2) 미로의 네 방향을 탐색하십시오 : 오른쪽은 오른쪽에 있고, 아래쪽은 아래쪽에 있고, 왼쪽은 왼쪽에 있고, 위로 올라가고, 출구로가는 도보 경로를 출력하십시오.
예:
왼쪽 상단 코너 (1, 1)는 입구이고 오른쪽 하단 (8, 9)은 출구입니다.
역 추적 방법, 즉 입구에서 시작하여 특정 방향으로 탐색 할 수 있습니다. 할 수 있다면 앞으로 나아가십시오. 그렇지 않으면 원래 경로를 따라 후퇴하고 출구 위치까지 다른 방향으로 계속 탐색하고 경로를 찾으십시오. 가능한 모든 경로가 탐색되고 출구에 도달하지 않으면 미로 세트에는 경로가 없습니다.
import java.util.*; 클래스 위치 {public position () {} public position (int row, int col) {this.col = col; this.row = 행; } public String toString () {return "(" + row + "," + col + ")"; } int 행; int col;} 클래스 미로 {public maze () {maze = new int [15] [15]; 스택 = 새 스택 <position> (); p = 새로운 부울 [15] [15]; } /** 미로 구성* / public void init () {스캐너 스캐너 = 새 스캐너 (System.In); System.out.println ( "미로 행의 수를 입력하십시오"); row = scanner.nextint (); System.out.println ( "미로의 열 수를 입력하십시오"); col = scanner.nextint (); System.out.println ( "" + row + "row" + col + "column maze"를 입력하십시오); int temp = 0; for (int i = 0; i <row; ++ i) {for (int j = 0; j <col; ++ j) {temp = scanner.nextInt (); 미로 [i] [J] = 온도; p [i] [j] = false; }}} /** 미로로 돌아가서 나가는 길 for (int i = 0; i <row +2; ++ i) {for (int j = 0; j <col +2; ++ j) {temp [0] [j] = 1; 온도 [row + 1] [j] = 1; 온도 [i] [0] = 온도 [i] [col + 1] = 1; }} // 원래 미로를 새 미로에 복사합니다 (int i = 0; i <row; ++ i) {for (int j = 0; j <col; ++ j) {temp [i +1] [j +1] = 미로 [i] [J]; }} // 왼쪽 상단에서 시계 방향으로 쿼리를 시작합니다 int i = 1; int j = 1; p [i] [j] = true; stack.push (새 위치 (i, j)); while (! stack.empty () && (! stack.push (새 위치 (i, j + 1)); J ++; } else if ((temp [i + 1] [j] == 0) && (p [i + 1] [j] == false)) {p [i + 1] [j] = true; stack.push (새 위치 (i + 1, j)); i ++; } else if ((temp [i] [j -1] == 0) && (p [i] [j -1] == false)) {p [i] [j -1] = true; stack.push (새 위치 (i, j -1)); J--; } else if ((temp [i -1] [j] == 0) && (p [i -1] [j] == false)) {p [i -1] [j] = true; stack.push (새 위치 (i -1, j)); 나--; } else {stack.pop (); if (stack.empty ()) {break; } i = stack.peek (). 행; j = stack.peek (). col; }} stack <position> newpos = new Stack <position> (); if (stack.empty ()) {break; } i = stack.peek (). 행; j = stack.peek (). col; }} stack <position> newpos = new Stack <position> (); if (stack.empty ()) {system.out.println ( "경로 없음"); } else {system.out.println ( "경로가 있습니다"); System.out.println ( "경로는 다음과 같습니다 :"); while (! stack.empty ()) {position pos = new position (); pos = stack.pop (); newpos.push (pos); }} / * * 그래픽 출력 경로 * / 문자열 result [] [] = 새 문자열 [row+1] [col+1]; for (int k = 0; k <row; ++ k) {for (int t = 0; t <col; ++ t) {result [k] [t] = (Maze [k] [t])+""; }} while (! newpos.empty ()) {position p1 = newpos.pop (); 결과 [p1.row-1] [p1.col-1] = "#"; } for (int k = 0; k <row; ++ k) {for (int t = 0; t <col; ++ t) {system.out.print (Resault [k] [t]+"/t"); } system.out.println (); }} int 미로 [] []; 개인 int row = 9; 개인 int col = 8; 스택 <position> 스택; 부울 p [] [] = null;} class hello {public static void main (String [] args) {Maze demo = new Maze (); demo.init (); demo.findpath (); }} Running example:
미로 줄의 수를 입력하십시오
3
미로에 열 수를 입력하십시오
3
3 행과 3 개의 열의 미로를 입력하십시오
0 1 1
0 0 1
1 0 0
경로는 다음과 같습니다.
미로 줄의 수를 입력하십시오
9
미로에 열 수를 입력하십시오
8
9 줄과 8 열의 미로를 입력하십시오
0 0 1 0 0 1 0
0 0 1 0 0 1 0
0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0
0 1 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 1 0 1
1 1 0 0 0 0 0
경로는 다음과 같습니다.
위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.