DFS(深さ優先探索)とBFS(広さ優先探索)迷宮経路問題の総括を求める
問題のように、本編の博文の創作の目的は博主がDFSとBFSに対して迷宮の問題を解くいくつかの見方を総括することにある.
DFSの概要-DFSすなわち深さ優先探索アルゴリズムは、図の遍歴アルゴリズムの一つに属し、英語ではDFSすなわちDepth First Searchと略す.その検索プロセスは、簡単に言えば、可能なブランチパスごとにこれ以上深く入り込めないまで深く入り込み、ノードごとに1回しか検索されません.
個人のDFSに対する理解は:南の壁にぶつかって振り返らない(もしぶつかったら、振り向くかもしれないし、振り向かないかもしれない;振り向くと、振り向く過程を遡及と呼ぶ).具体的な問題では、どうすればいいか分からない問題に直面したとき(あるいは対応する数学モデルが見つからずに問題を解くとき)、深さ優先検索を使って問題を解くことがよくあります(実際には試行錯誤し続け、貧乏になる過程です)、深さ優先検索はこのような問題を解決するのに適しています.例えば迷宮の経路を解く(注意:ここでは経路を指し、必ずしも最短経路を指すとは限らない)問題は、古典的な探求過程である.
DFS迷路の例を見てみましょう.
问题描述:仮に迷路があるとしたら、この迷路は0、1という2つの文字からなり、0は通路を表し、歩くことができ、1は壁を表し、歩けない.迷宮の左上を起点にして、右下を終点にして、起点から上(U)下(D)左(L)右(R)の4つの方向に向かって歩くことしかできなくて、境界を越えてはいけなくて、壁を越えてはいけなくて、起点から終点まで全部で何本の経路(条数は出力しないことができます)があることを求めて、これらの経路はどんな様子です(経路の長さとU、D、L、Fからなる文字列を出力して経路を表す必要があります)、あなたが通った経路を'#'でマークし、迷路を出力します.注意:出力は順序を考慮しなくてもいいです.
迷宮は以下の通りです.
まず問題を審査し,問題は出力経路とその経路の下の迷宮を要求する.
構想分析:明らかに、テーマは私たちがすべての迷宮の経路を窮挙することであり、DFSでやることを容易に考え、次のコードがあります.
コード注意事項:Javaで実装したDFSですが、迷路はファイルから入力され、上の迷路平面図です.対応するエンジニアリングディレクトリの下に置いてください.そうしないとFIleNotFoundException異常が放出されます.
Javaができない学生がいることを考慮して、C++の書き方を添付して、迷宮のファイルはソースコードと同じディレクトリの下に置く必要があります
正しい場合、次の結果が得られます.
明らかにDFSは迷路のすべての経路を探し出す任務を立派に完成したが、明らかに無秩序である.そしてよく観察すると、DFSには意外なサプライズがある.それはDFSがすべての経路を探し出すと同時に迷路の最短経路を探し出したことだ.so surprise!
DFSプロセス分析:DFSがどのように正しい経路を検索したのか分からない仲間が多いと信じています.ブロガーも最初はよく分からなかったので、DFSの中間プロセスを出力しようとしました.それから分かりました.今、コードを少し変更します.DFSは結果を出力するだけでなく、プロセスも出力してみましょう.
変更後のコードは次のとおりです.
実行結果は次のとおりです.
以上の結果から,DFSの探索,遡及,出口への到達過程が明らかになったが,DFSの実行過程は分かったか.
DFSの検索プロセスを分析してみると、上に印刷したプロセスの結果から、DFSは格子で格子で探しています.障害に遭遇して、道が通じないことに気づいたとき、振り返って、それから探して、ゴールに着くまで、出力経路を探して、今回の試みを完成して、それから前の状態に戻って、探して、このように試してみることができます.すべての迷路の経路を探し出しました;それからすべての経路が探求し終わった時、DFSは迷路の初期状態に戻ります;総括的に言えば、DFSの長所は貧乏で、すべての状況を探し出すことができて、しかし欠点も明らかで、みんなが発見したかどうか分かりませんか?よし、関門を売らないで、DFSの欠点は毎回1つの格子で1つの格子のように歩いています.この歩き方は効率が低すぎて、小さな迷路を処理してもいいですが、大きな迷路に遭遇すると、出られない可能性が高いです.例えば、次の迷路です.
これは30*50の迷路ですが、DFSをそのまま使って貧乏に行くと、その時間は泣きたくなるほど待ちます.邪を信じない仲間が自分でやってみましょう.ブロガーは一度やってみたことがありますが、計算しても一日も経っていません.だから、この場合はDFSを使って解くべきではありません.あるいは単純なDFSを使って解くべきではありません.DFSの効率を高める方法を考えなければなりません.例えば枝を切る.
上の大きな迷路はDFS+枝切りで検索した部分の答えは以下の通りです.完全な答えファイルは3つのGを超えています.それは恐ろしいデータ量です.だから、本文は一部の答えだけを貼ります.
上記の出力では、ブロガーはDFSを簡単に最適化し、最適化された枝切り操作を行い、毎回経路がより小さいものだけを検索するので、この出力は順序があります.枝切りのコードを貼り付けます.
このような大きな迷路は,明らかにすべての経路を出力しようとするが,そのデータ量は恐ろしいので,この問題は迷路を求める最短経路(最適解)になることが多い.問題は、上記の結果から分かるように、DFSは明らかにこのような大量の貧乏な試みに適していないことが明らかになり、時間がかかりすぎて、そこでこの時、本編の博文の第2のアルゴリズムBFSを順調に引き出すことができるようになった.
BFS概要——BFS即ち広さ優先アルゴリズム(Breadth-First Search)「幅優先探索」または「横優先探索」とも呼ばれ、BFSと略称される図の探索アルゴリズムである.簡単に言えば、BFSは図の起点から始まり、隣接する各ノードを同時に探索し、ターゲットが発見されると探索は終了する.個人的には、BFSは実際には、ある合法的な経路が見つかるまで、各可能な経路を同時に歩む.
博主はDFSとBFSに対する理解:博主はDFSを一人で迷宮を歩いていることを理解して、この人は仕事をするのがとても機械的で、迷宮を持って行って、彼は順番に歩くことができる経路を探るだけで、毎回1本だけ探して、彼が分岐点に出会った時、彼は勝手にその中の1本を選んで、歩いて、彼が壁に出会って、歩いていけないことを発見して、この時彼は振り向いて、帰って分岐点、それから次の歩くことができる経路を試して、彼が運がよくて、ある経路に沿って、終点に着いた時、彼も振り向いて、前の分岐点まで歩いて、まだ別の経路があるかどうかを試して、迷路を出ることができて、上述の過程を繰り返して、彼がすべての経路を歩き終わるまで、彼は迷路の起点に戻ります.ブロガーはBFSを無数の人が同時に迷路を歩いて、彼らは迷路を歩いて一定の策略に従って、この策略は、毎回歩く前に、すべて次の歩くことができる経路をメモして、すべての人は異なる存在する可能性のある経路を歩いて、終点まで歩きます.DFSとBFSの主な違いはDFSが1本の道で黒(南の壁にぶつかって振り返らない)まで歩くことですDFSは一般的な理解では窮屈な試みに適しており、BFSは最適解の試みに適している.DFSもBFSも方向性がないため、検索のたびに結果が異なる可能性がある.
今BFS迷宮の例を見てみると、同じように上の迷宮で、テーマは少し変更されていますが、現在は最短経路と最短経路を出力する迷宮の歩き方だけが要求されています.
DFSの敷居ができて、そこで直接BFSのコードに上がって、大体DFSのコードに似ていますが、ここではキューを借りて次のノードを保存します.
C++コードも添付します.
BFSで得られた結果
簡単に最短経路を求めたのではないでしょうか.そして今、その大きな迷路も入れてみましょう.
同様に最短経路を簡単に求めた.ほぼ秒解と言える.
注意:実は迷路を求める最短経路には穴があります.同じ長さの経路が複数同時に存在する可能性があるので、このときどの経路が最適解なのでしょうか.ブロガーは上記の処理は経路の辞書順で、私はちょっとしたテクニックを使って、遍歴方向に優先的に処理しました.もちろん優秀な皆さんも他の方法で処理することができますああ、本文はあまり述べません.
最後に述べたように,DFSは窮挙演算に適しており,BFSは最適解計算に適している.
DFSの概要-DFSすなわち深さ優先探索アルゴリズムは、図の遍歴アルゴリズムの一つに属し、英語ではDFSすなわちDepth First Searchと略す.その検索プロセスは、簡単に言えば、可能なブランチパスごとにこれ以上深く入り込めないまで深く入り込み、ノードごとに1回しか検索されません.
個人のDFSに対する理解は:南の壁にぶつかって振り返らない(もしぶつかったら、振り向くかもしれないし、振り向かないかもしれない;振り向くと、振り向く過程を遡及と呼ぶ).具体的な問題では、どうすればいいか分からない問題に直面したとき(あるいは対応する数学モデルが見つからずに問題を解くとき)、深さ優先検索を使って問題を解くことがよくあります(実際には試行錯誤し続け、貧乏になる過程です)、深さ優先検索はこのような問題を解決するのに適しています.例えば迷宮の経路を解く(注意:ここでは経路を指し、必ずしも最短経路を指すとは限らない)問題は、古典的な探求過程である.
DFS迷路の例を見てみましょう.
问题描述:仮に迷路があるとしたら、この迷路は0、1という2つの文字からなり、0は通路を表し、歩くことができ、1は壁を表し、歩けない.迷宮の左上を起点にして、右下を終点にして、起点から上(U)下(D)左(L)右(R)の4つの方向に向かって歩くことしかできなくて、境界を越えてはいけなくて、壁を越えてはいけなくて、起点から終点まで全部で何本の経路(条数は出力しないことができます)があることを求めて、これらの経路はどんな様子です(経路の長さとU、D、L、Fからなる文字列を出力して経路を表す必要があります)、あなたが通った経路を'#'でマークし、迷路を出力します.注意:出力は順序を考慮しなくてもいいです.
迷宮は以下の通りです.
010000
000100
001001
110000まず問題を審査し,問題は出力経路とその経路の下の迷宮を要求する.
構想分析:明らかに、テーマは私たちがすべての迷宮の経路を窮挙することであり、DFSでやることを容易に考え、次のコードがあります.
package wiki.zimo;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* dfs
* @author
* @datetime 2019 3 29 3:23:10
*/
public class Dfs {
public static void main(String[] args) throws FileNotFoundException {
Scanner in = new Scanner(new FileInputStream(new File("src/map.txt")));
List list = new ArrayList<>();
while (in.hasNext()) {
list.add(in.nextLine());
}
char map[][] = new char[list.size()][list.get(0).length()];
for (int i = 0; i < list.size(); i++) {
String temp = list.get(i);
map[i] = temp.toCharArray();
}
Point start = new Point(0, 0);
Point end = new Point(map.length - 1, map[0].length - 1);
dfs(map,start,end);
}
//
static int dirX[] = {-1,0,1,0};
static int dirY[] = {0,1,0,-1};
static char directions[] = {'U','R','D','L'};
public static void dfs(char[][] map, Point current, Point end) {
//
if (current.x == end.x && current.y == end.y) {
String path = current.path;
System.out.println(path.length()+","+path);
map[current.x][current.y] = '#';
printMap(map);
return;
}
map[current.x][current.y] = '#';
for (int k = 0; k < 4; k++) {
int x = current.x + dirX[k];
int y = current.y + dirY[k];
String path = current.path + directions[k];
Point temp = new Point(x, y, path);
if (temp.x >= 0 && temp.x < map.length && temp.y >= 0 && temp.y < map[temp.x].length && map[temp.x][temp.y] == '0') {
map[temp.x][temp.y] = '#';
dfs(map, temp, end);
//
map[temp.x][temp.y] = '0';
}
}
}
public static void printMap(char map[][]) {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
System.out.println();
}
static class Point{
int x;
int y;
String path;//
public Point(int x,int y) {
this(x, y ,"");
}
public Point(int x,int y,String path) {
this.x = x;
this.y = y;
this.path = path;
}
}
}
コード注意事項:Javaで実装したDFSですが、迷路はファイルから入力され、上の迷路平面図です.対応するエンジニアリングディレクトリの下に置いてください.そうしないとFIleNotFoundException異常が放出されます.
Javaができない学生がいることを考慮して、C++の書き方を添付して、迷宮のファイルはソースコードと同じディレクトリの下に置く必要があります
#include
#include
using namespace std;
#define MAX_R 100
#define MAX_C 100
#define R 4
#define C 6
class Point{
public:
int x;
int y;
string path;
Point(int x,int y,string path)
{
this->x = x;
this->y = y;
this->path = path;
}
Point(int x,int y)
{
new (this) Point(x,y,"");//
}
};
void printMap(char map[MAX_R][MAX_C])
{
for(int i = 0;i < R;i++)
{
for(int j = 0;j < C;j++)
{
cout< 正しい場合、次の結果が得られます.
12,DRRURRRDLDDR
#1####
###1##
0010#1
1100##
14,DRRURRRDLDLDRR
#1####
###1##
001##1
110###
10,DRRURRDDDR
#1###0
###1#0
0010#1
1100##
12,DRRURRDDLDRR
#1###0
###1#0
001##1
110###
14,DDRURURRRDLDDR
#1####
###1##
##10#1
1100##
16,DDRURURRRDLDLDRR
#1####
###1##
##1##1
110###
12,DDRURURRDDDR
#1###0
###1#0
##10#1
1100##
14,DDRURURRDDLDRR
#1###0
###1#0
##1##1
110###明らかにDFSは迷路のすべての経路を探し出す任務を立派に完成したが、明らかに無秩序である.そしてよく観察すると、DFSには意外なサプライズがある.それはDFSがすべての経路を探し出すと同時に迷路の最短経路を探し出したことだ.so surprise!
DFSプロセス分析:DFSがどのように正しい経路を検索したのか分からない仲間が多いと信じています.ブロガーも最初はよく分からなかったので、DFSの中間プロセスを出力しようとしました.それから分かりました.今、コードを少し変更します.DFSは結果を出力するだけでなく、プロセスも出力してみましょう.
変更後のコードは次のとおりです.
package wiki.zimo;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* dfs
* @author
* @datetime 2019 3 29 3:23:10
*/
public class Dfs {
public static void main(String[] args) throws FileNotFoundException {
Scanner in = new Scanner(new FileInputStream(new File("src/map.txt")));
List list = new ArrayList<>();
while (in.hasNext()) {
list.add(in.nextLine());
}
char map[][] = new char[list.size()][list.get(0).length()];
for (int i = 0; i < list.size(); i++) {
String temp = list.get(i);
map[i] = temp.toCharArray();
}
Point start = new Point(0, 0);
Point end = new Point(map.length - 1, map[0].length - 1);
dfs(map,start,end);
}
//
static int dirX[] = {-1,0,1,0};
static int dirY[] = {0,1,0,-1};
static char directions[] = {'U','R','D','L'};
public static void dfs(char[][] map, Point current, Point end) {
//
if (current.x == end.x && current.y == end.y) {
System.out.println(" ");// ，
String path = current.path;
System.out.println(path.length()+","+path);
map[current.x][current.y] = '#';
printMap(map);
return;
}
map[current.x][current.y] = '#';
for (int k = 0; k < 4; k++) {
int x = current.x + dirX[k];
int y = current.y + dirY[k];
String path = current.path + directions[k];
Point temp = new Point(x, y, path);
if (temp.x >= 0 && temp.x < map.length && temp.y >= 0 && temp.y < map[temp.x].length && map[temp.x][temp.y] == '0') {
System.out.println(" ");// ，
printMap(map);// ，
map[temp.x][temp.y] = '#';
dfs(map, temp, end);
//
System.out.println(" ");// ，
printMap(map);// ，
map[temp.x][temp.y] = '0';
}
}
}
public static void printMap(char map[][]) {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
System.out.println();
}
static class Point{
int x;
int y;
String path;//
public Point(int x,int y) {
this(x, y ,"");
}
public Point(int x,int y,String path) {
this.x = x;
this.y = y;
this.path = path;
}
}
}
実行結果は次のとおりです.
#10000
000100
001001
110000
#10000
#00100
001001
110000
#10000
##0100
001001
110000
#10000
###100
001001
110000
#1#000
###100
001001
110000
#1##00
###100
001001
110000
#1###0
###100
001001
110000
#1####
###100
001001
110000
#1####
###10#
001001
110000
#1####
###1##
001001
110000
#1####
###1##
0010#1
110000
#1####
###1##
0010#1
1100#0
12,DRRURRRDLDDR
#1####
###1##
0010#1
1100##
#1####
###1##
0010#1
1100##
#1####
###1##
0010#1
1100#0
#1####
###1##
0010#1
110##0
#1####
###1##
001##1
110##0
#1####
###1##
0010#1
110##0
#1####
###1##
0010#1
11###0
#1####
###1##
0010#1
110##0
#1####
###1##
0010#1
1100#0
#1####
###1##
0010#1
110000
#1####
###1##
001##1
110000
#1####
###1##
001##1
110#00
#1####
###1##
001##1
110##0
14,DRRURRRDLDLDRR
#1####
###1##
001##1
110###
#1####
###1##
001##1
110###
#1####
###1##
001##1
110##0
#1####
###1##
001##1
110#00
#1####
###1##
001##1
11##00
#1####
###1##
001##1
110#00
#1####
###1##
001##1
110000
#1####
###1##
0010#1
110000
#1####
###1##
001001
110000
#1####
###10#
001001
110000
#1####
###100
001001
110000
#1###0
###100
001001
110000
#1###0
###1#0
001001
110000
#1###0
###1##
001001
110000
#1####
###1##
001001
110000
#1###0
###1##
001001
110000
#1###0
###1#0
001001
110000
#1###0
###1#0
0010#1
110000
#1###0
###1#0
0010#1
1100#0
10,DRRURRDDDR
#1###0
###1#0
0010#1
1100##
#1###0
###1#0
0010#1
1100##
#1###0
###1#0
0010#1
1100#0
#1###0
###1#0
0010#1
110##0
#1###0
###1#0
001##1
110##0
#1###0
###1#0
0010#1
110##0
#1###0
###1#0
0010#1
11###0
#1###0
###1#0
0010#1
110##0
#1###0
###1#0
0010#1
1100#0
#1###0
###1#0
0010#1
110000
#1###0
###1#0
001##1
110000
#1###0
###1#0
001##1
110#00
#1###0
###1#0
001##1
110##0
12,DRRURRDDLDRR
#1###0
###1#0
001##1
110###
#1###0
###1#0
001##1
110###
#1###0
###1#0
001##1
110##0
#1###0
###1#0
001##1
110#00
#1###0
###1#0
001##1
11##00
#1###0
###1#0
001##1
110#00
#1###0
###1#0
001##1
110000
#1###0
###1#0
0010#1
110000
#1###0
###1#0
001001
110000
#1###0
###100
001001
110000
#1##00
###100
001001
110000
#1#000
###100
001001
110000
#10000
###100
001001
110000
#10000
##0100
001001
110000
#10000
##0100
0#1001
110000
#10000
##0100
##1001
110000
#10000
##0100
0#1001
110000
#10000
##0100
001001
110000
#10000
#00100
001001
110000
#10000
#00100
#01001
110000
#10000
#00100
##1001
110000
#10000
##0100
##1001
110000
#10000
###100
##1001
110000
#1#000
###100
##1001
110000
#1##00
###100
##1001
110000
#1###0
###100
##1001
110000
#1####
###100
##1001
110000
#1####
###10#
##1001
110000
#1####
###1##
##1001
110000
#1####
###1##
##10#1
110000
#1####
###1##
##10#1
1100#0
14,DDRURURRRDLDDR
#1####
###1##
##10#1
1100##
#1####
###1##
##10#1
1100##
#1####
###1##
##10#1
1100#0
#1####
###1##
##10#1
110##0
#1####
###1##
##1##1
110##0
#1####
###1##
##10#1
110##0
#1####
###1##
##10#1
11###0
#1####
###1##
##10#1
110##0
#1####
###1##
##10#1
1100#0
#1####
###1##
##10#1
110000
#1####
###1##
##1##1
110000
#1####
###1##
##1##1
110#00
#1####
###1##
##1##1
110##0
16,DDRURURRRDLDLDRR
#1####
###1##
##1##1
110###
#1####
###1##
##1##1
110###
#1####
###1##
##1##1
110##0
#1####
###1##
##1##1
110#00
#1####
###1##
##1##1
11##00
#1####
###1##
##1##1
110#00
#1####
###1##
##1##1
110000
#1####
###1##
##10#1
110000
#1####
###1##
##1001
110000
#1####
###10#
##1001
110000
#1####
###100
##1001
110000
#1###0
###100
##1001
110000
#1###0
###1#0
##1001
110000
#1###0
###1##
##1001
110000
#1####
###1##
##1001
110000
#1###0
###1##
##1001
110000
#1###0
###1#0
##1001
110000
#1###0
###1#0
##10#1
110000
#1###0
###1#0
##10#1
1100#0
12,DDRURURRDDDR
#1###0
###1#0
##10#1
1100##
#1###0
###1#0
##10#1
1100##
#1###0
###1#0
##10#1
1100#0
#1###0
###1#0
##10#1
110##0
#1###0
###1#0
##1##1
110##0
#1###0
###1#0
##10#1
110##0
#1###0
###1#0
##10#1
11###0
#1###0
###1#0
##10#1
110##0
#1###0
###1#0
##10#1
1100#0
#1###0
###1#0
##10#1
110000
#1###0
###1#0
##1##1
110000
#1###0
###1#0
##1##1
110#00
#1###0
###1#0
##1##1
110##0
14,DDRURURRDDLDRR
#1###0
###1#0
##1##1
110###
#1###0
###1#0
##1##1
110###
#1###0
###1#0
##1##1
110##0
#1###0
###1#0
##1##1
110#00
#1###0
###1#0
##1##1
11##00
#1###0
###1#0
##1##1
110#00
#1###0
###1#0
##1##1
110000
#1###0
###1#0
##10#1
110000
#1###0
###1#0
##1001
110000
#1###0
###100
##1001
110000
#1##00
###100
##1001
110000
#1#000
###100
##1001
110000
#10000
###100
##1001
110000
#10000
##0100
##1001
110000
#10000
#00100
##1001
110000
#10000
#00100
#01001
110000
#10000
#00100
001001
110000以上の結果から,DFSの探索,遡及,出口への到達過程が明らかになったが,DFSの実行過程は分かったか.
DFSの検索プロセスを分析してみると、上に印刷したプロセスの結果から、DFSは格子で格子で探しています.障害に遭遇して、道が通じないことに気づいたとき、振り返って、それから探して、ゴールに着くまで、出力経路を探して、今回の試みを完成して、それから前の状態に戻って、探して、このように試してみることができます.すべての迷路の経路を探し出しました;それからすべての経路が探求し終わった時、DFSは迷路の初期状態に戻ります;総括的に言えば、DFSの長所は貧乏で、すべての状況を探し出すことができて、しかし欠点も明らかで、みんなが発見したかどうか分かりませんか?よし、関門を売らないで、DFSの欠点は毎回1つの格子で1つの格子のように歩いています.この歩き方は効率が低すぎて、小さな迷路を処理してもいいですが、大きな迷路に遭遇すると、出られない可能性が高いです.例えば、次の迷路です.
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000これは30*50の迷路ですが、DFSをそのまま使って貧乏に行くと、その時間は泣きたくなるほど待ちます.邪を信じない仲間が自分でやってみましょう.ブロガーは一度やってみたことがありますが、計算しても一日も経っていません.だから、この場合はDFSを使って解くべきではありません.あるいは単純なDFSを使って解くべきではありません.DFSの効率を高める方法を考えなければなりません.例えば枝を切る.
上の大きな迷路はDFS+枝切りで検索した部分の答えは以下の通りです.完全な答えファイルは3つのGを超えています.それは恐ろしいデータ量です.だから、本文は一部の答えだけを貼ります.
318,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUUUUURUURUUUURURRDDDRRRDDDRDDLDLDDRRURDDRDDRDLDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUUULDLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRURDDDDRRDLLDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##011###10000001###10100110###1001
1100011#1####111##10##1#0101010101#1010100011#1000
0001000#1##1#00##101#01#1010111010#0101010100##101
111##10#1010#10#1000#10####1010101#1##10010001#100
000###1##000##1#1011#01111#1000110####1010101##011
101#1#1##1110###100##11000#1011001111#1101000#1000
101#1#1#1####110101#100101##00101#####1110111#1001
100#0###1#11###100##1011001#11010#101110000###0100
101#1##1##00###101#0100001##01000#010001111#101001
001#1##1#101#11010#101010##110101#110111####110101
110#101##001##0011#000001#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101##10101#1#1111101##10
00000100101000###110010100101##10000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001###
1000001010010100101011000000010#101#10001011101###
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
316,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUUUUURUURUUUURURRDDDRRRDDDRDDLDLDDRRURDDRDDRDLDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUUULDLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRURDDDDRDLDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##011###10000001###10100110###1001
1100011#1####111##10##1#0101010101#1010100011#1000
0001000#1##1#00##101#01#1010111010#0101010100##101
111##10#1010#10#1000#10####1010101#1##10010001#100
000###1##000##1#1011#01111#1000110####1010101##011
101#1#1##1110###100##11000#1011001111#1101000#1000
101#1#1#1####110101#100101##00101#####1110111#1001
100#0###1#11###100##1011001#11010#101110000###0100
101#1##1##00###101#0100001##01000#010001111#101001
001#1##1#101#11010#101010##110101#110111####110101
110#101##001##0011#000001#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101##10101#1#1111101##10
00000100101000###110010100101##10000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001##0
1000001010010100101011000000010#101#10001011101##0
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
314,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUUUUURUURUUUURURRDDDRRRDDDRDDLDLDDRRURDDRDDRDLDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUUULDLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRURDDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##011###10000001###10100110###1001
1100011#1####111##10##1#0101010101#1010100011#1000
0001000#1##1#00##101#01#1010111010#0101010100##101
111##10#1010#10#1000#10####1010101#1##10010001#100
000###1##000##1#1011#01111#1000110####1010101##011
101#1#1##1110###100##11000#1011001111#1101000#1000
101#1#1#1####110101#100101##00101#####1110111#1001
100#0###1#11###100##1011001#11010#101110000###0100
101#1##1##00###101#0100001##01000#010001111#101001
001#1##1#101#11010#101010##110101#110111####110101
110#101##001##0011#000001#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101##10101#1#1111101##10
00000100101000###110010100101##10000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
312,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUUUUURUURUUUURURRDDDRRRDDDRDDLDLDDRRURDDRDDRDLDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUUULDLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##011###10000001###10100110###1001
1100011#1####111##10##1#0101010101#1010100011#1000
0001000#1##1#00##101#01#1010111010#0101010100##101
111##10#1010#10#1000#10####1010101#1##10010001#100
000###1##000##1#1011#01111#1000110####1010101##011
101#1#1##1110###100##11000#1011001111#1101000#1000
101#1#1#1####110101#100101##00101#####1110111#1001
100#0###1#11###100##1011001#11010#101110000###0100
101#1##1##00###101#0100001##01000#010001111#101001
001#1##1#101#11010#101010##110101#110111####110101
110#101##001##0011#000001#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101##10101#1#11111010010
00000100101000###110010100101##10000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
310,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUUUUURUURUUUURURRDDDRRRDDDRDDLDLDDRRURDDRDDRDLDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##011###10000001###10100110###1001
1100011#1####111##10##1#0101010101#1010100011#1000
0001000#1##1#00##101#01#1010111010#0101010100##101
111##10#1010#10#1000#10####1010101#10010010001#100
000###1##000##1#1011#01111#1000110####1010101##011
101#1#1##1110###100##11000#1011001111#1101000#1000
101#1#1#1####110101#100101##00101#####1110111#1001
100#0###1#11###100##1011001#11010#101110000###0100
101#1##1##00###101#0100001##01000#010001111#101001
001#1##1#101#11010#101010##110101#110111####110101
110#101##001##0011#000001#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101##10101#1#11111010010
00000100101000###110010100101##10000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
308,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUUUUURUURUUUURURRDDDRRRDDDRDDLDLDDRRURDDRDDDDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##011###10000001###10100110###1001
1100011#1####111##10##1#0101010101#1010100011#1000
0001000#1##1#00##101#01#1010111010#0101010100##101
111##10#1010#10#1000#10####1010101#10010010001#100
000###1##000##1#1011#01111#1000110####1010101##011
101#1#1##1110###100##11000#1011001111#1101000#1000
101#1#1#1####110101#100101##00101#####1110111#1001
100#0###1#11###100##1011001#11010#101110000###0100
101#1##1##00###101#0100001##01000#010001111#101001
001#1##1#101#11010#101010##110101#110111####110101
110#101##001##0011#000001#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101#010101#1#11111010010
00000100101000###110010100101#010000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
306,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUUUUURUURUUUURURRDDDRRRDDDRDDLDLDDRRRDRDDDDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##011###10000001###10100110###1001
1100011#1####111##10##1#0101010101#1010100011#1000
0001000#1##1#00##101#01#1010111010#0101010100##101
111##10#1010#10#1000#10####1010101#10010010001#100
000###1##000##1#1011#01111#1000110####1010101##011
101#1#1##1110###100##11000#1011001111#1101000#1000
101#1#1#1####110101#100101##00101#####1110111#1001
100#0###1#11###100##1011001#11010#101110000###0100
101#1##1##00###101#0100001##01000#010001111#101001
001#1##1#101#11010#101010##110101#110111####110101
110#101##001##0011#000001#1001010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101#010101#1#11111010010
00000100101000###110010100101#010000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
304,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUURRRRUURRUUURRDRDDLDLDDRRURDDRDDRDLDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUUULDLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRURDDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#1##10010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###10000110###1011001111#1101000#1000
101#1#1#1####11010101001#1##00101#####1110111#1001
100#0###1#11###100001011#01#11010#101110000###0100
101#1##1##00###1010010###1##01000#010001111#101001
001#1##1#101#110100101#10##110101#110111####110101
110#101##001##0011#####01#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101##10101#1#1111101##10
00000100101000###110010100101##10000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
302,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUURRRRUURRUUURRDRDDLDLDDRRURDDRDDRDLDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUUULDLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#1##10010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###10000110###1011001111#1101000#1000
101#1#1#1####11010101001#1##00101#####1110111#1001
100#0###1#11###100001011#01#11010#101110000###0100
101#1##1##00###1010010###1##01000#010001111#101001
001#1##1#101#110100101#10##110101#110111####110101
110#101##001##0011#####01#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101##10101#1#11111010010
00000100101000###110010100101##10000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
300,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUURRRRUURRUUURRDRDDLDLDDRRURDDRDDRDLDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#10010010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###10000110###1011001111#1101000#1000
101#1#1#1####11010101001#1##00101#####1110111#1001
100#0###1#11###100001011#01#11010#101110000###0100
101#1##1##00###1010010###1##01000#010001111#101001
001#1##1#101#110100101#10##110101#110111####110101
110#101##001##0011#####01#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101##10101#1#11111010010
00000100101000###110010100101##10000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
298,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUURRRRUURRUUURRDRDDLDLDDRRURDDRDDDDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#10010010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###10000110###1011001111#1101000#1000
101#1#1#1####11010101001#1##00101#####1110111#1001
100#0###1#11###100001011#01#11010#101110000###0100
101#1##1##00###1010010###1##01000#010001111#101001
001#1##1#101#110100101#10##110101#110111####110101
110#101##001##0011#####01#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101#010101#1#11111010010
00000100101000###110010100101#010000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
296,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUURRRRUURRUUURRDRDDLDLDDRRRDRDDDDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#10010010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###10000110###1011001111#1101000#1000
101#1#1#1####11010101001#1##00101#####1110111#1001
100#0###1#11###100001011#01#11010#101110000###0100
101#1##1##00###1010010###1##01000#010001111#101001
001#1##1#101#110100101#10##110101#110111####110101
110#101##001##0011#####01#1001010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101#010101#1#11111010010
00000100101000###110010100101#010000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
294,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUURRRRUURRDRDDRRURDDRDDRDLDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUUULDLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRURDDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#1##10010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###100001100001011001111#1101000#1000
101#1#1#1####11010101001010000101#####1110111#1001
100#0###1#11###100001011001011010#101110000###0100
101#1##1##00###1010010###10001000#010001111#101001
001#1##1#101#110100101#1##0110101#110111####110101
110#101##001##0011#####01#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101##10101#1#1111101##10
00000100101000###110010100101##10000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
292,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUURRRRUURRDRDDRRURDDRDDRDLDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUUULDLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#1##10010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###100001100001011001111#1101000#1000
101#1#1#1####11010101001010000101#####1110111#1001
100#0###1#11###100001011001011010#101110000###0100
101#1##1##00###1010010###10001000#010001111#101001
001#1##1#101#110100101#1##0110101#110111####110101
110#101##001##0011#####01#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101##10101#1#11111010010
00000100101000###110010100101##10000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
290,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUURRRRUURRDRDDRRURDDRDDRDLDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#10010010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###100001100001011001111#1101000#1000
101#1#1#1####11010101001010000101#####1110111#1001
100#0###1#11###100001011001011010#101110000###0100
101#1##1##00###1010010###10001000#010001111#101001
001#1##1#101#110100101#1##0110101#110111####110101
110#101##001##0011#####01#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101##10101#1#11111010010
00000100101000###110010100101##10000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
288,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUURRRRUURRDRDDRRURDDRDDDDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#10010010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###100001100001011001111#1101000#1000
101#1#1#1####11010101001010000101#####1110111#1001
100#0###1#11###100001011001011010#101110000###0100
101#1##1##00###1010010###10001000#010001111#101001
001#1##1#101#110100101#1##0110101#110111####110101
110#101##001##0011#####01#1##1010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101#010101#1#11111010010
00000100101000###110010100101#010000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
286,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUURRRRUURRDRDDRRRDRDDDDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#10010010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###100001100001011001111#1101000#1000
101#1#1#1####11010101001010000101#####1110111#1001
100#0###1#11###100001011001011010#101110000###0100
101#1##1##00###1010010###10001000#010001111#101001
001#1##1#101#110100101#1##0110101#110111####110101
110#101##001##0011#####01#1001010####10##111000010
000#10##1100##1101#110100####1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101#010101#1#11111010010
00000100101000###110010100101#010000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
284,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUURRRRRDRRRRURDDRDDDDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#10010010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###100001100001011001111#1101000#1000
101#1#1#1####11010101001010000101#####1110111#1001
100#0###1#11###100001011001011010#101110000###0100
101#1##1##00###101001000010001000#010001111#101001
001#1##1#101#11010010101000110101#110111####110101
110#101##001##0011######101##1010####10##111000010
000#10##1100##1101#1101######1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101#010101#1#11111010010
00000100101000###110010100101#010000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
282,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRUURRRRRDRRRRRDRDDDDDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#10010010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###100001100001011001111#1101000#1000
101#1#1#1####11010101001010000101#####1110111#1001
100#0###1#11###100001011001011010#101110000###0100
101#1##1##00###101001000010001000#010001111#101001
001#1##1#101#11010010101000110101#110111####110101
110#101##001##0011######101001010####10##111000010
000#10##1100##1101#1101######1001010#10#1000011101
101#01#10001#100###000111011##101101#11#1010100001
001#1##00100##11#101010000100#100010#1##0100010101
101###0100011##1#001000010101#010101#1#11111010010
00000100101000###110010100101#010000#1##########10
11010000001001110111001001000#111010#1011011101#00
00000110100010001000100000001###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
280,DDDDRRURRRRRRRDRRUUURRDRRDRRURRURDDDLLLDLLDDRDRDLDLDDDLLULUUULLDLUULLDDDDRDLDDLDDLUUUUULULDDDDDDDDDDDRRURUURURUURUURRRDRRDLLDDRDLDDRDRDRRUUURRRRDDDDRDRRRRRURRRDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100###10101##10000100000001##11##110100101
#1111011010#1###1####011010010111###1100#####10000
#1########1#101###11#1000010100###1010101011##1011
###111110###00101####1001010001#1000001011000##000
110010001101010###1010110001101##1101010101111#111
000110110101010#1001001010000001#0010100111####000
101000001010001##110101010111110#1100001000#111010
0011100###101010##01100010000001###10100110###1001
1100011#1####111##1000100101010101#1010100011#1000
0001000#1##1#00##10100101010111010#0101010100##101
111##10#1010#10#100001000001010101#10010010001#100
000###1##000##1#101100111101000110####1010101##011
101#1#1##1110###100001100001011001111#1101000#1000
101#1#1#1####11010101001010000101#####1110111#1001
100#0###1#11###100001011001011010#101110000###0100
101#1##1##00###101001000010001000#010001111#101001
001#1##1#101#11010010101000110101#110111####110101
110#101##001##0011000000101001010####10##111000010
000#10##1100##1101011010000001001010#10#1000011101
101#01#10001#100#####011101100101101#11#1010100001
001#1##00100##11#101#100001000100010#1##0100010101
101###0100011##1#001#000101010010101#1#11111010010
00000100101000###110#101001010010000#1##########10
11010000001001110111##1001####111010#1011011101#00
000001101000100010001######01###0111#1000000110#11
1010100010100010001000111110001#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
上記の出力では、ブロガーはDFSを簡単に最適化し、最適化された枝切り操作を行い、毎回経路がより小さいものだけを検索するので、この出力は順序があります.枝切りのコードを貼り付けます.
package wiki.zimo;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* dfs ， ，
* @author
* @datetime 2019 3 29 3:23:10
*/
public class Dfs {
public static void main(String[] args) throws FileNotFoundException {
Scanner in = new Scanner(new FileInputStream(new File("src/map.txt")));
List list = new ArrayList<>();
while (in.hasNext()) {
list.add(in.nextLine());
}
char map[][] = new char[list.size()][list.get(0).length()];
for (int i = 0; i < list.size(); i++) {
String temp = list.get(i);
map[i] = temp.toCharArray();
}
Point start = new Point(0, 0);
Point end = new Point(map.length - 1, map[0].length - 1);
dfs(map,start,end);
}
// ，
// static int dirX[] = {1,0,0,-1};
// static int dirY[] = {0,-1,1,0};
// static char directions[] = {'D','L','R','U'};
static int dirX[] = {-1,0,1,0};
static int dirY[] = {0,1,0,-1};
static char directions[] = {'U','R','D','L'};
static int minStep = Integer.MAX_VALUE;
public static void dfs(char[][] map, Point current, Point end) {
//
if (current.x == end.x && current.y == end.y) {
if (minStep > current.path.length()) {
minStep = current.path.length();
}
String path = current.path;
System.out.println(path.length()+","+path);
map[current.x][current.y] = '#';
printMap(map);
return;
}
map[current.x][current.y] = '#';
for (int k = 0; k < 4; k++) {
int x = current.x + dirX[k];
int y = current.y + dirY[k];
String path = current.path + directions[k];
Point temp = new Point(x, y, path);
//
if (path.length() >= minStep) {
return;
}
if (temp.x >= 0 && temp.x < map.length && temp.y >= 0 && temp.y < map[temp.x].length && map[temp.x][temp.y] == '0') {
map[temp.x][temp.y] = '#';
dfs(map, temp, end);
//
map[temp.x][temp.y] = '0';
}
}
}
public static void printMap(char map[][]) {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
System.out.println();
}
static class Point{
int x;
int y;
String path;//
public Point(int x,int y) {
this(x, y ,"");
}
public Point(int x,int y,String path) {
this.x = x;
this.y = y;
this.path = path;
}
}
}
このような大きな迷路は,明らかにすべての経路を出力しようとするが,そのデータ量は恐ろしいので,この問題は迷路を求める最短経路(最適解)になることが多い.問題は、上記の結果から分かるように、DFSは明らかにこのような大量の貧乏な試みに適していないことが明らかになり、時間がかかりすぎて、そこでこの時、本編の博文の第2のアルゴリズムBFSを順調に引き出すことができるようになった.
BFS概要——BFS即ち広さ優先アルゴリズム(Breadth-First Search)「幅優先探索」または「横優先探索」とも呼ばれ、BFSと略称される図の探索アルゴリズムである.簡単に言えば、BFSは図の起点から始まり、隣接する各ノードを同時に探索し、ターゲットが発見されると探索は終了する.個人的には、BFSは実際には、ある合法的な経路が見つかるまで、各可能な経路を同時に歩む.
博主はDFSとBFSに対する理解:博主はDFSを一人で迷宮を歩いていることを理解して、この人は仕事をするのがとても機械的で、迷宮を持って行って、彼は順番に歩くことができる経路を探るだけで、毎回1本だけ探して、彼が分岐点に出会った時、彼は勝手にその中の1本を選んで、歩いて、彼が壁に出会って、歩いていけないことを発見して、この時彼は振り向いて、帰って分岐点、それから次の歩くことができる経路を試して、彼が運がよくて、ある経路に沿って、終点に着いた時、彼も振り向いて、前の分岐点まで歩いて、まだ別の経路があるかどうかを試して、迷路を出ることができて、上述の過程を繰り返して、彼がすべての経路を歩き終わるまで、彼は迷路の起点に戻ります.ブロガーはBFSを無数の人が同時に迷路を歩いて、彼らは迷路を歩いて一定の策略に従って、この策略は、毎回歩く前に、すべて次の歩くことができる経路をメモして、すべての人は異なる存在する可能性のある経路を歩いて、終点まで歩きます.DFSとBFSの主な違いはDFSが1本の道で黒(南の壁にぶつかって振り返らない)まで歩くことですDFSは一般的な理解では窮屈な試みに適しており、BFSは最適解の試みに適している.DFSもBFSも方向性がないため、検索のたびに結果が異なる可能性がある.
今BFS迷宮の例を見てみると、同じように上の迷宮で、テーマは少し変更されていますが、現在は最短経路と最短経路を出力する迷宮の歩き方だけが要求されています.
DFSの敷居ができて、そこで直接BFSのコードに上がって、大体DFSのコードに似ていますが、ここではキューを借りて次のノードを保存します.
package wiki.zimo;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
/**
* bfs
* @author
* @datetime 2019 3 29 7:12:59
*/
public class Bfs {
public static void main(String[] args) throws FileNotFoundException {
Scanner in = new Scanner(new FileInputStream(new File("src/map1.txt")));
List list = new ArrayList<>();
while (in.hasNext()) {
list.add(in.nextLine());
}
char map[][] = new char[list.size()][list.get(0).length()];
char originalMap[][] = new char[list.size()][list.get(0).length()];
for (int i = 0; i < list.size(); i++) {
String temp = list.get(i);
for (int j = 0; j < temp.length(); j++) {
map[i] = temp.toCharArray();
originalMap[i] = temp.toCharArray();
}
}
Point start = new Point(0,0);
Point end = new Point(map.length - 1, map[0].length - 1);
bfs(start,end,map,originalMap);
}
// ，
static int dirX[] = {1,0,0,-1};
static int dirY[] = {0,-1,1,0};
static char directions[] = {'D','L','R','U'};
public static void bfs(Point current, Point end, char[][] map,char[][] originalMap) {
Queue queue = new LinkedList<>();
queue.add(current);
while (!queue.isEmpty()) {
current = queue.poll();
//
if (current.x == end.x && current.y == end.y) {
String path = current.path;
Point temp = new Point(0, 0);
// ， '#' ,
originalMap[temp.x][temp.y] = '#';
for (int i = 0; i < path.length(); i++) {
char ch = path.charAt(i);
switch (ch) {
case 'U':
temp.x = temp.x - 1;
break;
case 'D':
temp.x = temp.x + 1;
break;
case 'L':
temp.y = temp.y - 1;
break;
case 'R':
temp.y = temp.y + 1;
break;
}
originalMap[temp.x][temp.y] = '#';
}
//
System.out.println(path.length()+","+path);
printMap(originalMap);
}
//
for (int i = 0; i < 4; i++) {
int x = current.x + dirX[i];
int y = current.y + dirY[i];
String path = current.path + directions[i];
Point temp = new Point(x, y, path);
if (temp.x >= 0 && temp.x < map.length && temp.y >= 0 && temp.y < map[0].length && map[temp.x][temp.y] == '0') {
queue.add(temp);
map[temp.x][temp.y] = '#';
}
}
}
}
public static void printMap(char map[][]) {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
/*if (map[i][j] == '#') {
System.out.print('#');
}else {
System.out.print(' ');
}*/
System.out.print(map[i][j]);
}
System.out.println();
}
System.out.println();
}
static class Point{
int x;
int y;
String path;//
public Point(int x,int y) {
this(x, y ,"");
}
public Point(int x,int y,String path) {
this.x = x;
this.y = y;
this.path = path;
}
}
}
C++コードも添付します.
#include
#include
#include
using namespace std;
#define MAX_R 100
#define MAX_C 100
#define R 4
#define C 6
class Point{
public:
int x;
int y;
string path;
Point(int x,int y,string path)
{
this->x = x;
this->y = y;
this->path = path;
}
Point(int x,int y)
{
new (this) Point(x,y,"");//
}
};
void printMap(char map[MAX_R][MAX_C])
{
for(int i = 0;i < R;i++)
{
for(int j = 0;j < C;j++)
{
cout< BFSで得られた結果
10,DRRURRDDDR
#1###0
###1#0
0010#1
1100##
簡単に最短経路を求めたのではないでしょうか.そして今、その大きな迷路も入れてみましょう.
186,DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#10101010010110010010101100101101001####1000101010
#0001000100000101010010000100000001##11#0110100101
#11110110100100010000011010010111###110######10000
#1#######0101010001101000010100###1010101011#01011
###11111#####010100001001010001#100000101100###000
110010001101#100001010110001101##1101010101111#111
000110110101#1001001001010000001#0010100111####000
10100000101##0100110101010111110#1100001000#111010
00111000001#10100001100010000001###10100110###1001
11000110100##111001000100101010101#1010100011#1000
000100001001#000010100101010111010#0101010100##101
111001001010#100100001000001010101#10010010001#100
000000100000#010101100111101000110####1010101##011
101010100111#000100001100001011001111#1101000#1000
101010101000#11010101001010000101#####1110111#1001
100000001011#00100001011001011010#101110000###0100
101010010000#00101001000010001000#010001111#101001
001010010101#11010010101000110101#110111####110101
110010100001#00011000000101001010###010##111000010
000010001100#0110101101000000100101##10#1000011101
101001010001#10000###011101100101101#11#1010100001
001010000100##1101#1#100001000100010#1##0100010101
1010000100011#01###1#000101010010101#1#11111010010
0000010010100####110#101001010010000#1##########10
11010000001001110111##10010000111010#1011011101#00
000001101000100010001#######1###0111#1000000110#11
101010001010001000100011111###1#101##1010000001#00
1000001010010100101011000000010#101#10001011101#00
0011110000100001000000011011100#####01000000001#11
10000001100111010111010001000110111010101101111###
同様に最短経路を簡単に求めた.ほぼ秒解と言える.
注意:実は迷路を求める最短経路には穴があります.同じ長さの経路が複数同時に存在する可能性があるので、このときどの経路が最適解なのでしょうか.ブロガーは上記の処理は経路の辞書順で、私はちょっとしたテクニックを使って、遍歴方向に優先的に処理しました.もちろん優秀な皆さんも他の方法で処理することができますああ、本文はあまり述べません.
最後に述べたように,DFSは窮挙演算に適しており,BFSは最適解計算に適している.