ラビリンス(Java BFSキュー)
29249 ワード
迷宮ラビリンス
【問題の説明】
次の図は、1とマークされた障害物、0とマークされた通行可能な場所を示す迷路の平面図です.010000,000,000,100,001,110,000迷宮の入り口は左上角、出口は右下角で、迷宮の中で、1つの位置からこの上、下、左、右の4つの方向の1つしか歩けません.上の迷路については、入口からDRRURRDDDRの順に迷路を通過することができ、全部で10歩です.このうちD,U,L,Rはそれぞれ下,上,左,右を表す.次のようなより複雑な迷路(30行50列)については、迷路を通過する方法を見つけてください.使用するステップ数が最も少なく、ステップ数が最も少ない前提の下で、辞書の順序が最も小さいものを答えとして見つけてください.ディクショナリシーケンスDでは、コピーされた内容がドキュメントと一致しているかどうかを確認する必要があります.試験問題ディレクトリの下にファイルmaze.txtがあります.内容は下記のテキストと同じです)010101010010010010010010101100010010010010010010010010100000101010010010010100000100100100101011010111101101001000001000000110101001110100100000010100000101010100000010010010010010010010010110010010100100111110100000101010010010010010100000101010010100000101010010100000101010010010100000101010010010010010100100100100100100101010010010101101101100100100100100101101101101100100100100100101101101101100100100110110110110110110110110110110010101001001001010000001000101001110000000 10100000101000100110101010111110011000010000111010 00111000001010100001100010000001000101001100001001 11000110100001110010001001010101010101010001101000 00010000100100000101001010101110100010101010000101 11100100101001001000010000010101010100100100010100 00000010000000101011001111010001100000101010100011 10101010011100001000011000010110011110110100001000 10101010100001101010100101000010100000111011101001 10000000101100010000101100101101001011100000000100 10101001000000010100100001000100000100011110101001 00101001010101101001010100011010101101110000110101 11001010000100001100000010100101000001000111000010 00001000110000110101101000000100101001001000011101 10100101000101000000001110110010110101101010100001 00101000010000110101010000100010001001000100010101 10100001000110010001000010101001010101011111010010 00000100101000000110010100101001000001000000000010 11010000001001110111001001000011101001011011101000 00000110100010001000100000001000011101000000110011 10101000101000100010001111100010101001010000001000 10000010100101001010110000000100101010001011101000 00111100001000010000000110111000000001000000001011 10000001100111010111010001000110111010101101111000
【回答提出】
これは結果を記入する問題で、結果を算出して提出すればいいだけです.本題の結果は1文字列で、4文字D、U、L、Rが含まれており、回答を提出する際にこの文字列だけを記入し、余分な内容を記入すると得点できません.
構想を分析する.
4種類のアルファベットD、U、L、R、本題は辞書順の最小、最小ステップ数、対角点の問題のため、BFSを選択します!BFS広さ優先探索は,自分に最も近い層から1層1層最適解を対角に求める点である.一方,dfs深さ優先探索はできるだけ初期点から離れている.BFSとDFSはいずれもDULRの順序で辞書を探すことができるが、DFSであれば辞書の順序が最小であることを確保するのは難しい.DFSはできるだけ初期点から離れているため、複数のパスを出た後にもう一つのことをしなければならないことを意味し、ステップ数を比較する.「複数のパスから出る」ということは、辞書の順序が最小になることを意味し、再び辞書の順序を比較する必要があります.多くの穴が待っていることがわかります.ディクショナリシーケンスの最小、最小ステップ数、対角点が同じレベルの優先度であることを忘れないでください.BFSは最短経路を完全に満たし、最も近い点から一定の順序でチームに入って、各層の最後のステップ数を探しているので必然的にBFSです!出口が見つかったら直接最適です.BFSがノードを見つけたときに最短経路をどのように確定するか、前から後までであれば、前のノードには4つの方向があり、後から前へ方向を覚え、前のノードがどのようにこのノードに着いたのかを記録し、以下のコードは2人の先輩を参考にした.https://blog.csdn.net/qq_34202873/article/details/102832588 https://blog.csdn.net/bluecyan/article/details/89036101
コードは3ビットバグによって空ポインタ異常クラスを深く教えられた:NullPointerException,これはJavaのオブジェクト作成に関する質問です.私の別のブログを見てください.https://blog.csdn.net/duduhh/article/details/104594262 見終わったら--やはりJavaとC++は違う配列負の下付き異常:NegativeArrayException配列下付き境界異常:ArrayIndexOutOfBoundsExceptionとキュースタックの中に細部の穴がある!!
【問題の説明】
次の図は、1とマークされた障害物、0とマークされた通行可能な場所を示す迷路の平面図です.010000,000,000,100,001,110,000迷宮の入り口は左上角、出口は右下角で、迷宮の中で、1つの位置からこの上、下、左、右の4つの方向の1つしか歩けません.上の迷路については、入口からDRRURRDDDRの順に迷路を通過することができ、全部で10歩です.このうちD,U,L,Rはそれぞれ下,上,左,右を表す.次のようなより複雑な迷路(30行50列)については、迷路を通過する方法を見つけてください.使用するステップ数が最も少なく、ステップ数が最も少ない前提の下で、辞書の順序が最も小さいものを答えとして見つけてください.ディクショナリシーケンスDでは、コピーされた内容がドキュメントと一致しているかどうかを確認する必要があります.試験問題ディレクトリの下にファイルmaze.txtがあります.内容は下記のテキストと同じです)010101010010010010010010101100010010010010010010010010100000101010010010010100000100100100101011010111101101001000001000000110101001110100100000010100000101010100000010010010010010010010010110010010100100111110100000101010010010010010100000101010010100000101010010100000101010010010100000101010010010010010100100100100100100101010010010101101101100100100100100101101101101100100100100100101101101101100100100110110110110110110110110110110010101001001001010000001000101001110000000 10100000101000100110101010111110011000010000111010 00111000001010100001100010000001000101001100001001 11000110100001110010001001010101010101010001101000 00010000100100000101001010101110100010101010000101 11100100101001001000010000010101010100100100010100 00000010000000101011001111010001100000101010100011 10101010011100001000011000010110011110110100001000 10101010100001101010100101000010100000111011101001 10000000101100010000101100101101001011100000000100 10101001000000010100100001000100000100011110101001 00101001010101101001010100011010101101110000110101 11001010000100001100000010100101000001000111000010 00001000110000110101101000000100101001001000011101 10100101000101000000001110110010110101101010100001 00101000010000110101010000100010001001000100010101 10100001000110010001000010101001010101011111010010 00000100101000000110010100101001000001000000000010 11010000001001110111001001000011101001011011101000 00000110100010001000100000001000011101000000110011 10101000101000100010001111100010101001010000001000 10000010100101001010110000000100101010001011101000 00111100001000010000000110111000000001000000001011 10000001100111010111010001000110111010101101111000
【回答提出】
これは結果を記入する問題で、結果を算出して提出すればいいだけです.本題の結果は1文字列で、4文字D、U、L、Rが含まれており、回答を提出する際にこの文字列だけを記入し、余分な内容を記入すると得点できません.
構想を分析する.
4種類のアルファベットD、U、L、R、本題は辞書順の最小、最小ステップ数、対角点の問題のため、BFSを選択します!BFS広さ優先探索は,自分に最も近い層から1層1層最適解を対角に求める点である.一方,dfs深さ優先探索はできるだけ初期点から離れている.BFSとDFSはいずれもDULRの順序で辞書を探すことができるが、DFSであれば辞書の順序が最小であることを確保するのは難しい.DFSはできるだけ初期点から離れているため、複数のパスを出た後にもう一つのことをしなければならないことを意味し、ステップ数を比較する.「複数のパスから出る」ということは、辞書の順序が最小になることを意味し、再び辞書の順序を比較する必要があります.多くの穴が待っていることがわかります.ディクショナリシーケンスの最小、最小ステップ数、対角点が同じレベルの優先度であることを忘れないでください.BFSは最短経路を完全に満たし、最も近い点から一定の順序でチームに入って、各層の最後のステップ数を探しているので必然的にBFSです!出口が見つかったら直接最適です.BFSがノードを見つけたときに最短経路をどのように確定するか、前から後までであれば、前のノードには4つの方向があり、後から前へ方向を覚え、前のノードがどのようにこのノードに着いたのかを記録し、以下のコードは2人の先輩を参考にした.https://blog.csdn.net/qq_34202873/article/details/102832588 https://blog.csdn.net/bluecyan/article/details/89036101
import java.util.Scanner;
public class Map_BFS {
class node{
int x;
int y;
int pre;// Que
char to;// D L R U
node(int x1,int y1,int previous,char t){
this.x=x1;
this.y=y1;
this.pre=previous;//
this.to=t;
}
void set(int x1,int y1,int previous,char t){
this.x=x1;
this.y=y1;
this.pre=previous;//
this.to=t;
}
node copy(){
int x=this.x;
int y=this.y;
int pre=this.pre;
char to=this.to;
return new node(x,y,pre,to);
}
}
//dfs - Que
class Que{
node data[] =new node[1500];
int front =-1;
int rear=-1;
void push(node n){
data[++rear]=n;
}
}
public static void main(String[] args){
//Scanner reader = new Scanner(System.in);
Map_BFS main = new Map_BFS();
main.initMap();
}
void initMap(){
int[][] map=new int[30][50];//
int[][] book=new int[30][50];// 0 1
int n=30,m=50;
int[][] next={{1,0},{0,-1},{0,1},{-1,0}};//
Scanner sc=new Scanner(System.in);
for(int i=0;i<30;i++){
for(int j=0;j<50;j++){
map[i][j]=sc.nextInt();
}
}
node N=new node(0,0,0,'0');// Data[0]
Que Q=new Que();
Q.push(N.copy());
book[0][0]=1;
int flag=0;
while(Q.front<Q.rear){
Q.front++;//front
int nx,ny;
for(int i=0;i<4;i++){// bfs
int f=Q.front;
nx=Q.data[f].x+next[i][0];
ny=Q.data[f].y+next[i][1];
//
if ( nx>n-1||ny>m-1||nx<0||ny<0) {
continue;
}
// ？ ？
if(book[nx][ny]==0&&map[nx][ny]==0){
book[nx][ny]=1;//
// ( x,y, ， )
if (next[i][0]!=0) {
N.set(nx,ny,Q.front,(next[i][0] == 1 ? 'D' : 'U'));
} else if (next[i][1]!=0) {
N.set(nx,ny,Q.front,(next[i][1] == 1 ? 'R' : 'L'));
}
Q.push(N.copy());//
if(nx==n-1&&ny==m-1){//
flag=1;
break;
}
}
}
if(flag==1){
break;
}
}
// previous
int k=Q.rear;
int t;
while(k!=0){
t=k;
k=Q.data[t].pre;//
Q.data[t].pre=-1;
}
//
for(int i=0;i<=Q.rear;i++){
if(Q.data[i].pre==-1)
System.out.print(Q.data[i].to);
}
}
}
コードは3ビットバグによって空ポインタ異常クラスを深く教えられた:NullPointerException,これはJavaのオブジェクト作成に関する質問です.私の別のブログを見てください.https://blog.csdn.net/duduhh/article/details/104594262 見終わったら--やはりJavaとC++は違う配列負の下付き異常:NegativeArrayException配列下付き境界異常:ArrayIndexOutOfBoundsExceptionとキュースタックの中に細部の穴がある!!