m×n長方形の配列は迷路を表し、0と1はそれぞれ迷路の経路と障害を表します。迷路の設定のために出口から出口へのパスを見つけるためのプログラムを設計したり、パスがないという結論を引き出します。
(1)2次元配列に従って迷路のグラフを出力します。
(2)迷路の4つの方向を探索します。右は右に、下は下に、左は左に、上に上がって、出口から出口の入り口から散歩道を出力します。
例:
左上隅(1、1)は入り口で、右下隅(8、9)は出口です。
バックトラッキング方法、つまり入り口から始めて特定の方向に探索することができます。それができる場合は、前進し続けます。それ以外の場合は、元のパスに沿って後退し、出口位置まで別の方向に探索し続け、パスを見つけます。可能なすべてのパスが調査され、出口に到達しない場合、ラビリンスセットにはパスがありません。
import java.util。*; class position {public position(){} public position(int row、int col){this.col = col; this.row = row; } public string toString(){return "(" + row + "、" + col + ")"; } int row; int col;} class maze {public maze(){maze = new int [15] [15]; stack = new stack <position>(); p = new Boolean [15] [15]; } /**迷路の構築* / public void init(){scanner scanner = new scanner(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] = temp; p [i] [j] = false; }}} /**迷路に戻って、出て行く方法があるかどうかを確認します* / public void findPath(){//元の迷路の家の周りに壁の円を与えます。 for(int i = 0; i <row +2; ++ i){for(int j = 0; j <col +2; ++ j){temp [0] [j] = 1;温度[row + 1] [j] = 1; temp [i] [0] = temp [i] [col + 1] = 1; }} //元の迷路を新しい迷路にコピーします(int i = 0; i <row; ++ i){for(int j = 0; j <col; ++ j){temp [i +1] [j +1] = maze [i] [j]; }} //左上隅から時計回りにクエリを開始しますint i = 1; int j = 1; p [i] [j] = true; stack.push(new Position(i、j)); while(!stack.empty()&&(!(i ==(row)&&(j == col))))))))))))) 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()。row; j = stack.peek()。col; }} stack <position> newpos = new stack <position>(); if(stack.empty()){break; } i = stack.peek()。row; j = stack.peek()。col; }} stack <position> newpos = new stack <position>(); if(stack.empty()){system.out.println( "no path"); } else {system.out.println( "パスがあります"); System.out.println( "パスは次のとおりです。"); while(!stack.empty()){position pos = new position(); pos = stack.pop(); newpos.push(pos); }} / * *グラフィカル出力パス * * / string result [] [] = new String [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(); result [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 maze [] []; Private int row = 9; Private int col = 8; stack <position> stack; boolean p [] [] = null;} class hello {public static void main(string [] args){Maze demo = new Maze(); demo.init(); demo.findpath(); }}実行例:
迷路の列数を入力してください
3
迷路に列の数を入力してください
3
3列と3列の迷路を入力してください
0 1 1
0 0 1
1 0 0
パスは次のとおりです。
迷路の列数を入力してください
9
迷路に列の数を入力してください
8
9列と8列の迷路を入力してください
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0 0
パスは次のとおりです。
上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。