如题，本篇博文的创作目的在于总结博主对DFS和BFS求解迷宫问题的一些看法
DFS简介——DFS即深度优先搜索算法，属于图的遍历算法中的一种，英文缩写为DFS即Depth First Search.其搜索过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点都只会搜索一次。
个人对于DFS的理解是：不撞南墙不回头（如果撞了，那么可能回头，可能不回头；如果回头，那么回头的过程叫做回溯）。在具体的问题中，某些时候，当面对一些不知道该怎么去做的问题的时候（或者说找不到对应的数学模型去求解问题的时候），常常会使用深度优先搜索的方式去求解问题（实际上是一个不断试探，不断穷举的过程），深度优先搜索很适合解决这类问题，比如求解迷宫的路径（注意：这里说的是路径，不一定是指最短路径）问题，就是一个很经典的试探过程。
现在我们来看一个DFS走迷宫实例。
题目描述：假设有一个有一个迷宫，这个迷宫由0、1这两种字符组成，0代表通路，可以走，1代表墙壁，不能走；迷宫的左上角为起点，右下角为终点，只能从起点开始朝着上（U）下（D）左（L）右（R）四个方向走，不能超出边界，不能越过墙壁，求从起点到终点总共有多少条路径（条数可不用输出），这些路径是什么样子的（需输出路径长度和由U、D、L、F构成的字符串代表路径），用‘#’标记你走过的路径，输出迷宫。注意：输出可以不考虑顺序。
迷宫如下：
010000000100001001110000
首先审题，题目要求输出路径和该路径下的迷宫
思路分析：很显然，题目这是要我们穷举出所有的迷宫路径了，很容易就会想到用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 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<String> 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<iostream>#include <fstream>using namespace std;#define MAX_R 100#define MAX_C 100#define R 4#define C 6class 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<<map[i][j];}cout<<endl;}cout<<endl;}int dirX[] = {-1,0,1,0};int dirY[] = {0,1,0,-1};string directions[] = {"U","R","D","L"};void dfs(char map[MAX_R][MAX_C],Point current,Point end){if(current.x == end.x && current.y == end.y){map[current.x][current.y] = '#';cout<<current.path.size()<<","<<current.path<<endl;printMap(map);return;}map[current.x][current.y] = '#';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(x,y,path);if(temp.x >= 0 && temp.x < R && temp.y >= 0 && temp.y < C && map[temp.x][temp.y] == '0'){map[temp.x][temp.y] = '#';dfs(map,temp,end);// 回溯map[temp.x][temp.y] = '0';}}}int main(){ifstream in;in.open("map.txt");char map[MAX_R][MAX_C];for(int i = 0;i < R;i++){in>>map[i];cout<<map[i]<<endl;}cout<<endl;in.close();Point start(0,0);Point end(R-1,C-1);dfs(map,start,end);return 0;}
正确的情况下，会得到下面的结果：
12,DRRURRRDLDDR#1#######1##0010#11100##14,DRRURRRDLDLDRR#1#######1##001##1110###10,DRRURRDDDR#1###0###1#00010#11100##12,DRRURRDDLDRR#1###0###1#0001##1110###14,DDRURURRRDLDDR#1#######1####10#11100##16,DDRURURRRDLDLDRR#1#######1####1##1110###12,DDRURURRDDDR#1###0###1#0##10#11100##14,DDRURURRDDLDRR#1###0###1#0##1##1110###
很显然，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 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<String> 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;}}}
然后现在得到的执行结果是：
试探#10000000100001001110000试探#10000#00100001001110000试探#10000##0100001001110000试探#10000###100001001110000试探#1#000###100001001110000试探#1##00###100001001110000试探#1###0###100001001110000试探#1#######100001001110000试探#1#######10#001001110000试探#1#######1##001001110000试探#1#######1##0010#1110000试探#1#######1##0010#11100#0出口12,DRRURRRDLDDR#1#######1##0010#11100##回溯#1#######1##0010#11100##试探#1#######1##0010#11100#0试探#1#######1##0010#1110##0回溯#1#######1##001##1110##0试探#1#######1##0010#1110##0回溯#1#######1##0010#111###0回溯#1#######1##0010#1110##0回溯#1#######1##0010#11100#0试探#1#######1##0010#1110000试探#1#######1##001##1110000试探#1#######1##001##1110#00试探#1#######1##001##1110##0出口14,DRRURRRDLDLDRR#1#######1##001##1110###回溯#1#######1##001##1110###回溯#1#######1##001##1110##0试探#1#######1##001##1110#00回溯#1#######1##001##111##00回溯#1#######1##001##1110#00回溯#1#######1##001##1110000回溯#1#######1##0010#1110000回溯#1#######1##001001110000回溯#1#######10#001001110000回溯#1#######100001001110000试探#1###0###100001001110000试探#1###0###1#0001001110000试探#1###0###1##001001110000回溯#1#######1##001001110000回溯#1###0###1##001001110000试探#1###0###1#0001001110000试探#1###0###1#00010#1110000试探#1###0###1#00010#11100#0出口10,DRRURRDDDR#1###0###1#00010#11100##回溯#1###0###1#00010#11100##试探#1###0###1#00010#11100#0试探#1###0###1#00010#1110##0回溯#1###0###1#0001##1110##0试探#1###0###1#00010#1110##0回溯#1###0###1#00010#111###0回溯#1###0###1#00010#1110##0回溯#1###0###1#00010#11100#0试探#1###0###1#00010#1110000试探#1###0###1#0001##1110000试探#1###0###1#0001##1110#00试探#1###0###1#0001##1110##0出口12,DRRURRDDLDRR#1###0###1#0001##1110###回溯#1###0###1#0001##1110###回溯#1###0###1#0001##1110##0试探#1###0###1#0001##1110#00回溯#1###0###1#0001##111##00回溯#1###0###1#0001##1110#00回溯#1###0###1#0001##1110000回溯#1###0###1#00010#1110000回溯#1###0###1#0001001110000回溯#1###0###100001001110000回溯#1##00###100001001110000回溯#1#000###100001001110000回溯#10000###100001001110000试探#10000##0100001001110000试探#10000##01000#1001110000回溯#10000##0100##1001110000回溯#10000##01000#1001110000回溯#10000##0100001001110000试探#10000#00100001001110000试探#10000#00100#01001110000试探#10000#00100##1001110000试探#10000##0100##1001110000试探#10000###100##1001110000试探#1#000###100##1001110000试探#1##00###100##1001110000试探#1###0###100##1001110000试探#1#######100##1001110000试探#1#######10###1001110000试探#1#######1####1001110000试探#1#######1####10#1110000试探#1#######1####10#11100#0出口14,DDRURURRRDLDDR#1#######1####10#11100##回溯#1#######1####10#11100##试探#1#######1####10#11100#0试探#1#######1####10#1110##0回溯#1#######1####1##1110##0试探#1#######1####10#1110##0回溯#1#######1####10#111###0回溯#1#######1####10#1110##0回溯#1#######1####10#11100#0试探#1#######1####10#1110000试探#1#######1####1##1110000试探#1#######1####1##1110#00试探#1#######1####1##1110##0出口16,DDRURURRRDLDLDRR#1#######1####1##1110###回溯#1#######1####1##1110###回溯#1#######1####1##1110##0试探#1#######1####1##1110#00回溯#1#######1####1##111##00回溯#1#######1####1##1110#00回溯#1#######1####1##1110000回溯#1#######1####10#1110000回溯#1#######1####1001110000回溯#1#######10###1001110000回溯#1#######100##1001110000试探#1###0###100##1001110000试探#1###0###1#0##1001110000试探#1###0###1####1001110000回溯#1#######1####1001110000回溯#1###0###1####1001110000试探#1###0###1#0##1001110000试探#1###0###1#0##10#1110000试探#1###0###1#0##10#11100#0出口12,DDRURURRDDDR#1###0###1#0##10#11100##回溯#1###0###1#0##10#11100##试探#1###0###1#0##10#11100#0试探#1###0###1#0##10#1110##0回溯#1###0###1#0##1##1110##0试探#1###0###1#0##10#1110##0回溯#1###0###1#0##10#111###0回溯#1###0###1#0##10#1110##0回溯#1###0###1#0##10#11100#0试探#1###0###1#0##10#1110000试探#1###0###1#0##1##1110000试探#1###0###1#0##1##1110#00试探#1###0###1#0##1##1110##0出口14,DDRURURRDDLDRR#1###0###1#0##1##1110###回溯#1###0###1#0##1##1110###回溯#1###0###1#0##1##1110##0试探#1###0###1#0##1##1110#00回溯#1###0###1#0##1##111##00回溯#1###0###1#0##1##1110#00回溯#1###0###1#0##1##1110000回溯#1###0###1#0##10#1110000回溯#1###0###1#0##1001110000回溯#1###0###100##1001110000回溯#1##00###100##1001110000回溯#1#000###100##1001110000回溯#10000###100##1001110000回溯#10000##0100##1001110000回溯#10000#00100##1001110000回溯#10000#00100#01001110000回溯#10000#00100001001110000
通过以上结果，可以明显的看到DFS试探、回溯、到达出口的过程，现在明白DFS的执行过程了吗？
分析一下DFS的搜索过程，从上面打印的过程结果中我们可以看到，DFS是一个格子一个格子去试探的，当它遇到障碍，发现路走不通的时候，它就会回头，然后接着试探，直到到达终点，输出路径，完成本次试探，然后又回退到之前的状态，接着试探，这样就可以试探出所有迷宫的路径了；然后当所有的路径都试探完的时候，DFS会回退到迷宫的初始状态；总结来说，DFS的优点是穷举，可以试探出所有的情况，但是缺点也是很明显的，不知道大家发现了没有呢？好了不卖关子，DFS的缺点是每次都是一个格子一个格子那么走的，这种走法效率太低了，处理小迷宫还行，如果一旦遇到大迷宫，就很可能出不来了，比如说，下面这个迷宫。
010101010010110010010101100101101001000010001010100000100010000010101001000010000000100110011010010101111011010010001000001101001011100011000000010000010000000010101000110100001010000010101010110010110001111100000010100001001010001010000010110000000011001000110101000010101100011010011010101011110111000110110101010010010010100000010001010011100000001010000010100010011010101011111001100001000011101000111000001010100001100010000001000101001100001001110001101000011100100010010101010101010100011010000001000010010000010100101010111010001010101000010111100100101001001000010000010101010100100100010100000000100000001010110011110100011000001010101000111010101001110000100001100001011001111011010000100010101010100001101010100101000010100000111011101001100000001011000100001011001011010010111000000001001010100100000001010010000100010000010001111010100100101001010101101001010100011010101101110000110101110010100001000011000000101001010000010001110000100000100011000011010110100000010010100100100001110110100101000101000000001110110010110101101010100001001010000100001101010100001000100010010001000101011010000100011001000100001010100101010101111101001000000100101000000110010100101001000001000000000010110100000010011101110010010000111010010110111010000000011010001000100010000000100001110100000011001110101000101000100010001111100010101001010000001000100000101001010010101100000001001010100010111010000011110000100001000000011011100000000100000000101110000001100111010111010001000110111010101101111000
这是个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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##011###10000001###10100110###10011100011#1####111##10##1#0101010101#1010100011#10000001000#1##1#00##101#01#1010111010#0101010100##101111##10#1010#10#1000#10####1010101#1##10010001#100000###1##000##1#1011#01111#1000110####1010101##011101#1#1##1110###100##11000#1011001111#1101000#1000101#1#1#1####110101#100101##00101#####1110111#1001100#0###1#11###100##1011001#11010#101110000###0100101#1##1##00###101#0100001##01000#010001111#101001001#1##1#101#11010#101010##110101#110111####110101110#101##001##0011#000001#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101##10101#1#1111101##1000000100101000###110010100101##10000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001###1000001010010100101011000000010#101#10001011101###0011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##011###10000001###10100110###10011100011#1####111##10##1#0101010101#1010100011#10000001000#1##1#00##101#01#1010111010#0101010100##101111##10#1010#10#1000#10####1010101#1##10010001#100000###1##000##1#1011#01111#1000110####1010101##011101#1#1##1110###100##11000#1011001111#1101000#1000101#1#1#1####110101#100101##00101#####1110111#1001100#0###1#11###100##1011001#11010#101110000###0100101#1##1##00###101#0100001##01000#010001111#101001001#1##1#101#11010#101010##110101#110111####110101110#101##001##0011#000001#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101##10101#1#1111101##1000000100101000###110010100101##10000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001##01000001010010100101011000000010#101#10001011101##00011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##011###10000001###10100110###10011100011#1####111##10##1#0101010101#1010100011#10000001000#1##1#00##101#01#1010111010#0101010100##101111##10#1010#10#1000#10####1010101#1##10010001#100000###1##000##1#1011#01111#1000110####1010101##011101#1#1##1110###100##11000#1011001111#1101000#1000101#1#1#1####110101#100101##00101#####1110111#1001100#0###1#11###100##1011001#11010#101110000###0100101#1##1##00###101#0100001##01000#010001111#101001001#1##1#101#11010#101010##110101#110111####110101110#101##001##0011#000001#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101##10101#1#1111101##1000000100101000###110010100101##10000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##011###10000001###10100110###10011100011#1####111##10##1#0101010101#1010100011#10000001000#1##1#00##101#01#1010111010#0101010100##101111##10#1010#10#1000#10####1010101#1##10010001#100000###1##000##1#1011#01111#1000110####1010101##011101#1#1##1110###100##11000#1011001111#1101000#1000101#1#1#1####110101#100101##00101#####1110111#1001100#0###1#11###100##1011001#11010#101110000###0100101#1##1##00###101#0100001##01000#010001111#101001001#1##1#101#11010#101010##110101#110111####110101110#101##001##0011#000001#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101##10101#1#1111101001000000100101000###110010100101##10000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##011###10000001###10100110###10011100011#1####111##10##1#0101010101#1010100011#10000001000#1##1#00##101#01#1010111010#0101010100##101111##10#1010#10#1000#10####1010101#10010010001#100000###1##000##1#1011#01111#1000110####1010101##011101#1#1##1110###100##11000#1011001111#1101000#1000101#1#1#1####110101#100101##00101#####1110111#1001100#0###1#11###100##1011001#11010#101110000###0100101#1##1##00###101#0100001##01000#010001111#101001001#1##1#101#11010#101010##110101#110111####110101110#101##001##0011#000001#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101##10101#1#1111101001000000100101000###110010100101##10000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##011###10000001###10100110###10011100011#1####111##10##1#0101010101#1010100011#10000001000#1##1#00##101#01#1010111010#0101010100##101111##10#1010#10#1000#10####1010101#10010010001#100000###1##000##1#1011#01111#1000110####1010101##011101#1#1##1110###100##11000#1011001111#1101000#1000101#1#1#1####110101#100101##00101#####1110111#1001100#0###1#11###100##1011001#11010#101110000###0100101#1##1##00###101#0100001##01000#010001111#101001001#1##1#101#11010#101010##110101#110111####110101110#101##001##0011#000001#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101#010101#1#1111101001000000100101000###110010100101#010000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##011###10000001###10100110###10011100011#1####111##10##1#0101010101#1010100011#10000001000#1##1#00##101#01#1010111010#0101010100##101111##10#1010#10#1000#10####1010101#10010010001#100000###1##000##1#1011#01111#1000110####1010101##011101#1#1##1110###100##11000#1011001111#1101000#1000101#1#1#1####110101#100101##00101#####1110111#1001100#0###1#11###100##1011001#11010#101110000###0100101#1##1##00###101#0100001##01000#010001111#101001001#1##1#101#11010#101010##110101#110111####110101110#101##001##0011#000001#1001010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101#010101#1#1111101001000000100101000###110010100101#010000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#1##10010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###10000110###1011001111#1101000#1000101#1#1#1####11010101001#1##00101#####1110111#1001100#0###1#11###100001011#01#11010#101110000###0100101#1##1##00###1010010###1##01000#010001111#101001001#1##1#101#110100101#10##110101#110111####110101110#101##001##0011#####01#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101##10101#1#1111101##1000000100101000###110010100101##10000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#1##10010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###10000110###1011001111#1101000#1000101#1#1#1####11010101001#1##00101#####1110111#1001100#0###1#11###100001011#01#11010#101110000###0100101#1##1##00###1010010###1##01000#010001111#101001001#1##1#101#110100101#10##110101#110111####110101110#101##001##0011#####01#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101##10101#1#1111101001000000100101000###110010100101##10000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#10010010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###10000110###1011001111#1101000#1000101#1#1#1####11010101001#1##00101#####1110111#1001100#0###1#11###100001011#01#11010#101110000###0100101#1##1##00###1010010###1##01000#010001111#101001001#1##1#101#110100101#10##110101#110111####110101110#101##001##0011#####01#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101##10101#1#1111101001000000100101000###110010100101##10000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#10010010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###10000110###1011001111#1101000#1000101#1#1#1####11010101001#1##00101#####1110111#1001100#0###1#11###100001011#01#11010#101110000###0100101#1##1##00###1010010###1##01000#010001111#101001001#1##1#101#110100101#10##110101#110111####110101110#101##001##0011#####01#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101#010101#1#1111101001000000100101000###110010100101#010000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#10010010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###10000110###1011001111#1101000#1000101#1#1#1####11010101001#1##00101#####1110111#1001100#0###1#11###100001011#01#11010#101110000###0100101#1##1##00###1010010###1##01000#010001111#101001001#1##1#101#110100101#10##110101#110111####110101110#101##001##0011#####01#1001010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101#010101#1#1111101001000000100101000###110010100101#010000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#1##10010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###100001100001011001111#1101000#1000101#1#1#1####11010101001010000101#####1110111#1001100#0###1#11###100001011001011010#101110000###0100101#1##1##00###1010010###10001000#010001111#101001001#1##1#101#110100101#1##0110101#110111####110101110#101##001##0011#####01#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101##10101#1#1111101##1000000100101000###110010100101##10000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#1##10010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###100001100001011001111#1101000#1000101#1#1#1####11010101001010000101#####1110111#1001100#0###1#11###100001011001011010#101110000###0100101#1##1##00###1010010###10001000#010001111#101001001#1##1#101#110100101#1##0110101#110111####110101110#101##001##0011#####01#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101##10101#1#1111101001000000100101000###110010100101##10000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#10010010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###100001100001011001111#1101000#1000101#1#1#1####11010101001010000101#####1110111#1001100#0###1#11###100001011001011010#101110000###0100101#1##1##00###1010010###10001000#010001111#101001001#1##1#101#110100101#1##0110101#110111####110101110#101##001##0011#####01#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101##10101#1#1111101001000000100101000###110010100101##10000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#10010010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###100001100001011001111#1101000#1000101#1#1#1####11010101001010000101#####1110111#1001100#0###1#11###100001011001011010#101110000###0100101#1##1##00###1010010###10001000#010001111#101001001#1##1#101#110100101#1##0110101#110111####110101110#101##001##0011#####01#1##1010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101#010101#1#1111101001000000100101000###110010100101#010000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#10010010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###100001100001011001111#1101000#1000101#1#1#1####11010101001010000101#####1110111#1001100#0###1#11###100001011001011010#101110000###0100101#1##1##00###1010010###10001000#010001111#101001001#1##1#101#110100101#1##0110101#110111####110101110#101##001##0011#####01#1001010####10##111000010000#10##1100##1101#110100####1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101#010101#1#1111101001000000100101000###110010100101#010000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#10010010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###100001100001011001111#1101000#1000101#1#1#1####11010101001010000101#####1110111#1001100#0###1#11###100001011001011010#101110000###0100101#1##1##00###101001000010001000#010001111#101001001#1##1#101#11010010101000110101#110111####110101110#101##001##0011######101##1010####10##111000010000#10##1100##1101#1101######1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101#010101#1#1111101001000000100101000###110010100101#010000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#10010010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###100001100001011001111#1101000#1000101#1#1#1####11010101001010000101#####1110111#1001100#0###1#11###100001011001011010#101110000###0100101#1##1##00###101001000010001000#010001111#101001001#1##1#101#11010010101000110101#110111####110101110#101##001##0011######101001010####10##111000010000#10##1100##1101#1101######1001010#10#1000011101101#01#10001#100###000111011##101101#11#1010100001001#1##00100##11#101010000100#100010#1##0100010101101###0100011##1#001000010101#010101#1#1111101001000000100101000###110010100101#010000#1##########1011010000001001110111001001000#111010#1011011101#0000000110100010001000100000001###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###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##000110010001101010###1010110001101##1101010101111#111000110110101010#1001001010000001#0010100111####000101000001010001##110101010111110#1100001000#1110100011100###101010##01100010000001###10100110###10011100011#1####111##1000100101010101#1010100011#10000001000#1##1#00##10100101010111010#0101010100##101111##10#1010#10#100001000001010101#10010010001#100000###1##000##1#101100111101000110####1010101##011101#1#1##1110###100001100001011001111#1101000#1000101#1#1#1####11010101001010000101#####1110111#1001100#0###1#11###100001011001011010#101110000###0100101#1##1##00###101001000010001000#010001111#101001001#1##1#101#11010010101000110101#110111####110101110#101##001##0011000000101001010####10##111000010000#10##1100##1101011010000001001010#10#1000011101101#01#10001#100#####011101100101101#11#1010100001001#1##00100##11#101#100001000100010#1##0100010101101###0100011##1#001#000101010010101#1#1111101001000000100101000###110#101001010010000#1##########1011010000001001110111##1001####111010#1011011101#00000001101000100010001######01###0111#1000000110#111010100010100010001000111110001#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###
在上面这个输出中，博主简单的优化了一下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 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<String> 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显然不适合做这种很大量的穷举试探，耗时太久了，于是这个时候就可以顺理成章的引出本篇博文的第二种算法BFS了。
BFS简介——BFS即广度优先算法（Breadth-First Search），又称作宽度优先搜索，或横向优先搜索，简称BFS，是一种图的搜索算法。简单的说，BFS是从图的起点开始，同时搜索遍历每个和它相邻的节点，一旦发现目标，则搜索终止。个人理解，BFS实际上就是同时在走每条可能存在的路径，直到它找到某条合法的路径为止。
博主对DFS和BFS的理解：博主把DFS理解成一个人在走迷宫，这个人做事很机械，就拿走迷宫来说，他只会依次试探每条可以走的路径，每次只试探一条，当他遇到分叉口时，他会随意选择其中一条，走下去，直到他遇到墙，发现走不下去了，这个时候他会回头，回到分叉口，接着去尝试下一条可以走的路径，当他运气好，沿着某条路径，走到了终点时，他也会回头，走到上一个分叉口，去尝试还有没有另外一条路径，可以走出迷宫，重复上述的过程，直到他走完了所有的路径，他会回到迷宫起点。博主把BFS理解为无数个人在同时走迷宫，他们走迷宫按照一定的策略，这个策略是，每次走之前，都把下一次可以走的路径记下来，每个人走不同的可能存在的路径，直到走到终点为止。DFS和BFS主要的区别在于DFS是按一条路走到黑（不撞南墙不回头）的原则去试探，而BFS是按层级去试探。按照通俗的理解来讲，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 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<String> 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<Point> 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<iostream>#include <fstream>#include <queue>using namespace std;#define MAX_R 100#define MAX_C 100#define R 4#define C 6class 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<<map[i][j];}cout<<endl;}cout<<endl;}int dirX[] = {1,0,0,-1};int dirY[] = {0,-1,1,0};char directions[] = {'D','L','R','U'};void bfs(Point current,Point end,char map[MAX_R][MAX_C],char originalMap[MAX_R][MAX_C]){queue<Point> q;q.push(current);while(q.empty() != 1){current = q.front();q.pop();if(current.x == end.x && current.y == end.y){string path = current.path;Point temp(0,0);for(int i = 0;i < path.size();i++){char ch = path[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] = '#';}cout<<path.size()<<","<<path<<endl;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(x,y,path);if(temp.x >= 0 && temp.x < R && temp.y >= 0 && temp.y < C && map[temp.x][temp.y] == '0'){q.push(temp);map[temp.x][temp.y] = '#';}}}}int main(){ifstream in;in.open("map.txt");char map[MAX_R][MAX_C];char originalMap[MAX_R][MAX_C];for(int i = 0;i < R;i++){in>>map[i];cout<<map[i]<<endl;}for(int i = 0;i < R;i++){for(int j = 0;j < C;j++){originalMap[i][j] = map[i][j];}}cout<<endl;in.close();Point start(0,0);Point end(R-1,C-1);bfs(start,end,map,originalMap);return 0;}
BFS得到的结果
10,DRRURRDDDR#1###0###1#00010#11100##
是不是很轻松的就求出了最短路径呢，然后现在我们把那个大迷宫也放进去试试，
186,DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR#10101010010110010010101100101101001####1000101010#0001000100000101010010000100000001##11#0110100101#11110110100100010000011010010111###110######10000#1#######0101010001101000010100###1010101011#01011###11111#####010100001001010001#100000101100###000110010001101#100001010110001101##1101010101111#111000110110101#1001001001010000001#0010100111####00010100000101##0100110101010111110#1100001000#11101000111000001#10100001100010000001###10100110###100111000110100##111001000100101010101#1010100011#1000000100001001#000010100101010111010#0101010100##101111001001010#100100001000001010101#10010010001#100000000100000#010101100111101000110####1010101##011101010100111#000100001100001011001111#1101000#1000101010101000#11010101001010000101#####1110111#1001100000001011#00100001011001011010#101110000###0100101010010000#00101001000010001000#010001111#101001001010010101#11010010101000110101#110111####110101110010100001#00011000000101001010###010##111000010000010001100#0110101101000000100101##10#1000011101101001010001#10000###011101100101101#11#1010100001001010000100##1101#1#100001000100010#1##01000101011010000100011#01###1#000101010010101#1#111110100100000010010100####110#101001010010000#1##########1011010000001001110111##10010000111010#1011011101#00000001101000100010001#######1###0111#1000000110#11101010001010001000100011111###1#101##1010000001#001000001010010100101011000000010#101#10001011101#000011110000100001000000011011100#####01000000001#1110000001100111010111010001000110111010101101111###
同样很轻松的求出了最短路径。几乎可以算是秒解了。
注意：其实求迷宫的最短路径是有坑的，因为有可能同时存在多条相同长度的路径，那么这个时候哪一条才是最优解呢？博主在上面的处理是按路径的字典顺序，我用了一点小技巧，在遍历方向那里做了个优先级处理。当然优秀的大家也可以按照其他的方式来处理，本文就不做过多阐述了。
终上所述，DFS适合做穷举运算，BFS适合做最优解计算。
如果觉得《DFS（深度优先搜索）和BFS（广度优先搜索）求迷宫路径问题的总结》对你有帮助，请点赞、收藏，并留下你的观点哦！
