重庆建设教育协会网站,网站设计哪家公司好,宝塔wordpress建站教程,微信商城定制迷宫
配套视频讲解
关于dfs和bfs的区别讲解。 对于上图#xff0c;假设我们要找从1到5的最短路#xff0c;那么我们用dfs去找#xff0c;并且按照编号从大到小的顺序去找#xff0c;首先找到的路径如下#xff0c; 从节点1出发#xff0c;我们发现节点2可以走#xff…迷宫
配套视频讲解
关于dfs和bfs的区别讲解。 对于上图假设我们要找从1到5的最短路那么我们用dfs去找并且按照编号从大到小的顺序去找首先找到的路径如下 从节点1出发我们发现节点2可以走于是我们就走向了节点2然后又发现节点2可以走向节点4于是走向了节点4然后从节点4走向了节点5我们只是找到了一条从节点1到节点5的路径但是我们并不能确定是否是最短路径所以我们还需要继续去找。我们回退到节点4与节点4相连的节点3和节点5都已经被遍历过了所以我们回退到节点2与节点2相连的节点1和节点4都已经被遍历过了所以我们回退到节点1此时节点3也与节点1相连于是我们走向节点3后面的路径如下图所示 我们通过节点3走向了节点5。然后返回到节点3与节点3相连的节点1和节点5都已经被遍历过了所以我们回退到节点1此时与节点1相连的节点2和节点3都已经被遍历过了dfs退出。
我们找到了两条路径通过对比这两天路径的长度我们可以找到最短路径可以看出我们穷尽了所有从节点1到达节点5的路径。
接下来看一看bfs是怎么找的。 我们是用队列实现的bfs过程一开始队列里面只有起始点即[1]。从队列里面拿出一个节点即节点1然后去走此时节点1能够到达的所有节点。如上图所示bfs会同时向多个方向拓展节点1与节点2节点3相连那么第一步它会从节点1走向节点也会从节点1走向节点3。这时分别将节点2和节点3加入队列并且此时节点1已经出队即[2,3]。然后去走所有与节点2相连且没有被遍历过的节点再去走所有与节点3相连且没有被遍历过的节点如下图所示 第二步从节点3走到节点5也从节点2走向了节点4但是此时我发现已经走到终点了并且长度为2即便在后续遍历中我可以走到终点但是现在所到达的所有点长度已经是2了那么后续继续走长度一定比2大所以我可以确定此时的路径一定是最短路。
dfs题目分析
这一道题我们可以用dfs也可以用bfs但是对于迷宫最短路类题目最好的方法是bfs。通过这道题如果采用dfs来做需要用到dfs里的回溯和剪枝。
首先分析题意我们要找从起点到终点的最短路并且这个最短路的行走路线是字典序最小其实字典序最小好操作我们只需要在遍历上下左右四个方向的时候按照字典序从小到大的顺序遍历就行了。即
static char[] direct {D,L,R,U};
static int[] nexty {0,-1,1,0};
static int[] nextx {1,0,0,-1};接下来考虑如何找最短路对于dfs而言要找最短路我必须把当前可走的所有路都遍历结束后才能确定哪一条路是最短路对于某一个位置我当前向左走标记左边的节点为已遍历过并且把这个’L’存入走到终点后我再回退那么再次回到这个位置时我会选择其它可以走的方向那么我们要把左边的节点已遍历过的标记清空表示没有遍历过并且把在这里存入的’L’取出。即
for (int i 0; i 4; i) {int xx x nextx[i];int yy y nexty[i];if(xx 0 xx n yy 0 yy m visit[xx][yy] 0 map[xx][yy] 0) {visit[xx][yy] 1;path[s] direct[i];//更新路径......dfs(xx, yy, s1);visit[xx][yy] 0;//回溯 dfs返回的时候往往需要对之前做的标记进行重置 }}解释一下上述代码for (int i 0; i 4; i)表示四个方向遍历它遍历的顺序由nextx和nexty数组决定而我们在最开始就给他规定了遍历的顺序是按字典序从小到大遍历的。然后if语句一是判断下一个位置的坐标是否越界二是判断下一个位置是否之前被遍历过三是判断下一个位置是否可以走都没问题的话我就去走这个位置然后标记这个位置被走过并且存入此时走的方向visit[xx][yy] 1;path[s] direct[i];然后就是进入dfs那么这里dfs三个参数分别表示下一个位置的x坐标y坐标以及走到下一个位置走了几步。dfs结束后我要给visit标记复原即visit[xx][yy] 0;
上述是正常dfs以及回溯的过程接下来我们要加入剪枝。什么情况下我可以确定这条路一定不会成为答案也就是这条路的长度超过了我们此时记录的最短路的长度即
if(s step) {return;
}s表示我走到当前节点的步数step表示此时记录的最短路的长度我还没有走到终点步数就比最短路长那么它必然不会成为最短路所以后面就不需要遍历了直接返回。
还有第二种剪枝这个不太好想也是比较最短路的长度我们比较的是到达当前位置的长度以及在之前我走到该位置的最短长度。比如有一个点A我走到这里耗费了s步但是我之前记录我走到这里耗费了s1步而s1s那么说明我之前走到这里再向后走的路径一定比我现在走到这里再向后走的路径短那么此时我就没有必要遍历了。即
if(s dp[x][y]) {return;
}s表示我走到当前节点(x,y)的步数 d p [ x ] [ y ] dp[x][y] dp[x][y]表示我之前走到该节点的最短路。那么在dfs的过程中我们要更新dp数组
for (int i 0; i 4; i) {int xx x nextx[i];int yy y nexty[i];if(xx 0 xx n yy 0 yy m visit[xx][yy] 0 map[xx][yy] 0) {visit[xx][yy] 1;dp[xx][yy] Math.min(dp[xx][yy], s1);//更新dppath[s] direct[i];//更新路径dfs(xx, yy, s1);visit[xx][yy] 0;//回溯 dfs返回的时候往往需要对之前做的标记进行重置//path[s] ;}}在回溯的时候我们只回溯了visit数组为什么呢?dp数组不需要回溯因为它记录的就是一个全局的值即在我所有到达(x,y)点的路径中最短路径的长度。而path数组虽然需要回溯但是我们在下一个遍历的时候下一个的值会直接覆盖之前的值所以不需要特意给他回溯。那么你也可以理解有回溯即注释的那个地方//path[s] ;这里写和不写效果是一样的。
然后我们看当走到终点时如何处理
//判断是否走到终点
if(x n-1 y m-1) {if(s step) {//当前步数小于之前的最优值对结果进行一下记录step s;String string ;for (int i 0; i s; i) {//System.out.print( path[i] );string path[i];}//set.add(string);result string;}//System.out.println();
}判断一下此时走到终点的路径长度是否小于我之前记录的长度如果小于我要更新最短路径长度以及这条路径每一步走的方向。
最后这道题给我们的图是一个字符串我们可以把它转化成二维字符数组转化细节在shuju函数里。
dfs题目代码
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;public class Main{/** 在步数最少的前提下请找出字典序最小的一个作为答案* 如何保证找到的第一个路径一定是字典序最小的* 遍历的时候按照字典序从小到大的顺序去遍历* DLRU* DDRURRDDDR* DRRURRDDDR* 如何记录我们的路径* bfs * node{* xypath//走到当前节点的路径* }* path*/static int n 30;static int m 50;static char[][] map new char[n][m];static char[] direct {D,L,R,U};static int[] nexty {0,-1,1,0};static int[] nextx {1,0,0,-1};static int[][] visit new int[n][m];//dfsstatic char[] path new char[n*m1];static int step n*m1;static String result ;static SetString set new HashSetString();static int[][] dp new int[n][m];
public static void main(String[] args) {Scanner sc new Scanner(System.in);shuju();for(int i0;in;i){Arrays.fill(dp[i], n*m1);}sc.close();visit[0][0] 1;dfs(0,0,0);System.out.println(result);
}
private static void shuju() {// TODO Auto-generated method stubString string 01010101001011001001010110010110100100001000101010000010001000001010100100001000000010011001101001010111101101001000100000110100101110001100000001000001000000001010100011010000101000001010101011001011000111110000001010000100101000101000001011000000001100100011010100001010110001101001101010101111011100011011010101001001001010000001000101001110000000101000001010001001101010101111100110000100001110100011100000101010000110001000000100010100110000100111000110100001110010001001010101010101010001101000000100001001000001010010101011101000101010100001011110010010100100100001000001010101010010010001010000000010000000101011001111010001100000101010100011101010100111000010000110000101100111101101000010001010101010000110101010010100001010000011101110100110000000101100010000101100101101001011100000000100 //D - L - R - U1010100100000001010010000100010000010001111010100100101001010101101001010100011010101101110000110101110010100001000011000000101001010000010001110000100000100011000011010110100000010010100100100001110110100101000101000000001110110010110101101010100001001010000100001101010100001000100010010001000101011010000100011001000100001010100101010101111101001000000100101000000110010100101001000001000000000010110100000010011101110010010000111010010110111010000000011010001000100010000000100001110100000011001110101000101000100010001111100010101001010000001000100000101001010010101100000001001010100010111010000011110000100001000000011011100000000100000000101110000001100111010111010001000110111010101101111000;//将上面的一大串字符转为数组中存储且数组为int型仅存0 和 1两个值 int[][] moze new int[30][50];for (int i 0 ; i 30 ; i) {for(int j 0 ; j 50 ; j) {map[i][j] string.charAt(i*50j); //}}
}
private static void dfs(int x, int y, int s) {//s当前已经走的步数 走的路径的方向path[i] 表示第i步走的方向/* 剪枝* 1.s走到xy所需要的步数step当前记录的走完迷宫所需要的最短的步数sstep return* 2.dp[x][y] 当前走到xy点所需要的最短距离sdp[x][y] return* * * dfs{* 1.剪枝* 2.回溯* 3.递归* * }*///剪枝操作if(s step) {return;}if(s dp[x][y]) {return;}//判断是否走到终点if(x n-1 y m-1) {//System.out.print(--- x y );if(s step) {//当前步数小于之前的最优值对结果进行一下记录step s;String string ;for (int i 0; i s; i) {//System.out.print( path[i] );string path[i];}//set.add(string);result string;}//System.out.println();}for (int i 0; i 4; i) {int xx x nextx[i];int yy y nexty[i];if(xx 0 xx n yy 0 yy m visit[xx][yy] 0 map[xx][yy] 0) {visit[xx][yy] 1;dp[xx][yy] Math.min(dp[xx][yy], s1);//更新dppath[s] direct[i];//更新路径dfs(xx, yy, s1);visit[xx][yy] 0;//回溯 dfs返回的时候往往需要对之前做的标记进行重置}}
}
}
bfs题目分析
迷宫最短路问题最简单的做法就是使用bfs去做bfs与dfs的区别是bfs第一次走到终点的路径一定是最短路他不用把所有可行路径都遍历一次。接下来大致讲一下bfs的过程。
在bfs的过程我是同时多个方向扩展路径所以每一个点当前我走到这里需要的步数以及这条路上的方向我都要记录所以我要自己写一个节点类里面存了节点坐标和走到该点的一个路径这个路径既表示了这条路上每一步走的方向也表明了路的长度。x和y表示当前点的坐标pathString表示走到当前点的路径。
static class node{int x;int y;String pathString;public node(int x, int y, String pathString) {super();this.x x;this.y y;this.pathString pathString;}}首先把起点加入队列并标记起点已经被访问过
LinkedListnode queue new LinkedList();//申请一个队列
queue.add(new node(0, 0, ));//把起点放入队列
visit[0][0] 1;
String shunxv ;//记录最短路径然后依次从队列里面取出点直到队列为空。取出点后我们先判断该点是否为终点节点如果是说明我们找到了一条最短路后续不需要遍历了直接退出。否则我要向四个方向去遍历。通过if语句判断下一个位置的坐标是否越界下一个位置是否可走下一个位置是否已经被遍历过都满足的话我就可以走向下一个位置把它对应的信息添加到队列里面然后标记该位置已经被走过。
while(!queue.isEmpty()){node t queue.poll();int x1 t.x;int y1 t.y;String str1 t.pathString;if(x1n-1y1m-1){//判断是否走到终点shunxv str1;break;}for(int i0;i4;i){//向四个方向去遍历int x2 x1nextx[i];int y2 y1nexty[i];if(x20x2n-1y20y2m-1map[x2][y2]0visit[x2][y2]!1){queue.add(new node(x2, y2, str1direct[i]));visit[x2][y2]1;}}
}bfs题目代码
import java.util.LinkedList;
import java.util.Scanner;
public class Main{/** 在步数最少的前提下请找出字典序最小的一个作为答案* 如何保证找到的第一个路径一定是字典序最小的* 遍历的时候按照字典序从小到大的顺序去遍历* DLRU* DDRURRDDDR* DRRURRDDDR* 如何记录我们的路径* bfs * node{* xypath//走到当前节点的路径* }* path*/static class node{int x;int y;String pathString;public node(int x, int y, String pathString) {super();this.x x;this.y y;this.pathString pathString;}}static int n 30;static int m 50;static char[][] map new char[n][m];static char[] direct {D,L,R,U};static int[] nexty {0,-1,1,0};static int[] nextx {1,0,0,-1};static int[][] visit new int[n][m];static String res;
public static void main(String[] args) {Scanner sc new Scanner(System.in);shuju();sc.close();bfs();
}
private static void shuju() {// TODO Auto-generated method stubString string 01010101001011001001010110010110100100001000101010000010001000001010100100001000000010011001101001010111101101001000100000110100101110001100000001000001000000001010100011010000101000001010101011001011000111110000001010000100101000101000001011000000001100100011010100001010110001101001101010101111011100011011010101001001001010000001000101001110000000101000001010001001101010101111100110000100001110100011100000101010000110001000000100010100110000100111000110100001110010001001010101010101010001101000000100001001000001010010101011101000101010100001011110010010100100100001000001010101010010010001010000000010000000101011001111010001100000101010100011101010100111000010000110000101100111101101000010001010101010000110101010010100001010000011101110100110000000101100010000101100101101001011100000000100 //D - L - R - U1010100100000001010010000100010000010001111010100100101001010101101001010100011010101101110000110101110010100001000011000000101001010000010001110000100000100011000011010110100000010010100100100001110110100101000101000000001110110010110101101010100001001010000100001101010100001000100010010001000101011010000100011001000100001010100101010101111101001000000100101000000110010100101001000001000000000010110100000010011101110010010000111010010110111010000000011010001000100010000000100001110100000011001110101000101000100010001111100010101001010000001000100000101001010010101100000001001010100010111010000011110000100001000000011011100000000100000000101110000001100111010111010001000110111010101101111000;//将上面的一大串字符转为数组中存储且数组为int型仅存0 和 1两个值 int[][] moze new int[30][50];for (int i 0 ; i 30 ; i) {for(int j 0 ; j 50 ; j) {map[i][j] string.charAt(i*50j); //}}
}
private static void bfs() {// TODO Auto-generated method stubLinkedListnode queue new LinkedList();//申请一个队列queue.add(new node(0, 0, ));//把起点放入队列visit[0][0] 1;String shunxv ;//记录最短路径while(!queue.isEmpty()){node t queue.poll();int x1 t.x;int y1 t.y;String str1 t.pathString;if(x1n-1y1m-1){//判断是否走到终点shunxv str1;break;}for(int i0;i4;i){//向四个方向去遍历int x2 x1nextx[i];int y2 y1nexty[i];if(x20x2n-1y20y2m-1map[x2][y2]0visit[x2][y2]!1){queue.add(new node(x2, y2, str1direct[i]));visit[x2][y2]1;}}}System.out.println(shunxv);
}
}
