广搜（bfs）和 深搜（dfs）
先从广搜说起(bfs)
广搜，字面感觉就是广面的搜索，其实就是这样的，我认为可以把广度搜索看成一步步的蔓延，但是不一定要遍历到所有的元素，因为一旦你达到了边界的条件，问题就可以得到解决了，剩余的元素不需要再去遍历了；广搜，我认为是以队列形式进行动态蔓延，此处动态亦顺时针方向轮流，每一个循环的head的x,y坐标在不越界的情况下，可以向四个方向蔓延，一般，我们认为这四个方向是右—>下—>左—>上；其实无论是广度搜索还是深度搜索，最重要的就是你在这一层循环中，你要做什么，并且要符合规定（我认为通常是数组越界问题）；根据广搜的特点，我又从网上查了下，理解了一番之后，广搜适合于解决一个图中的最短的路径的问题，因为刚才提到了广搜不会遍历图中所有的元素，因为达到了边界条件之后（也就是问题解决了之后），它会直接break;所以此路径必为最短；
今天做了一天了快这一道题，其实不难，就是一直少考虑，一直没有考虑到最后一个E点这个边界条件，以此例题解释广搜。(注释淦的很认真）
C语言网 迷宫问题 题号1672
import java.util.Scanner;
class Queen{
int x = 0;
int y = 0;
int s = 0;
}
public class bfs {
static char c[][]; //此为 n * m地图
static int book[][];
static int next[][] = {{0,1},{1,0},{0,-1},{-1,0}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int sss = scanner.nextInt(); //此为组数，即输入的次数
Queen que[] = new Queen[10000];//此为存储地图中的每个元素,因为题目要求最大地图是100行,100列，故大小为100*100
for(int i=0;i<10000;i++) {
que[i] = new Queen();//此处别忘实例化，不然会抱空指针的错误
}
for(int ss=0;ss<sss;ss++) {//sss的实现
int n = scanner.nextInt(),m = scanner.nextInt();
int startx = 0,starty = 0,p = 0,q = 0;
c = new char[n][m]; //此为地图
book = new int[n][m]; //对地图上面的经过的点都要标记，初始化各个元素为0
for(int i=0;i<n;i++) {//此处for循环把输入的地图，用二维字符数组接收
String s = scanner.next();
for(int j=0;j<m;j++) {
c[i][j] = s.charAt(j);
if(c[i][j] == 'S') {
startx = i;
starty = j;
}
if(c[i][j] == 'E') {
p = i;
q = j;
}
}
}
int head = 0,tail = 0,tx = 0,ty = 0;//head 为头 tail 为尾 tx 为下点横坐标 ty 为下点纵坐标
que[tail].x = startx;
que[tail].y = starty;
que[tail].s = 0;
tail++;
book[startx][starty] = 1;//此行把起点标记
int flag = 0;//此处为结束标志，若问题解决，将其置1
while(head < tail) {
for(int k=0;k<4;k++) {
tx = que[head].x+next[k][0];
ty = que[head].y+next[k][1];
if(tx < 0 || tx > n-1 || ty < 0 || ty > m-1) { //此处判断越界否
continue;
}
if((c[tx][ty] == '-' || c[tx][ty] == 'E') && book[tx][ty] == 0) {//此处将tx,ty加入队列中
book[tx][ty] = 1;
que[tail].x = tx;
que[tail].y = ty;
que[tail].s = que[head].s+1;
tail++;
}
if(tx == p && ty == q) {
flag = 1;
break;
}
}
if(flag == 1) {
break;//任务完成，打破循环
}
head++;//此处为下一次蔓延做准备
}
if(flag == 1) {
System.out.println(que[tail-1].s);
}
else {
System.out.println(-1);
}
}
}
}
再论深搜（dfs)
深搜，亦先从字面意思理解，深搜，他讲究的就是深度，一个方向走往深处，遍历路过的元素，如可到达边界，此便为答案之一。我认为，深搜，额额真的感觉没有什么说的，和递归相似感觉，递归思想，学过这两个搜索，递归好像没印象了，对于他们之间的关系到此，网上查阅是递归是dfs实现的一种实现手段；我从理解上面来说，我认为递归是dfs的子集；dfs是通过递归这种思想来实现的。
下面是一道例题，是洛谷上面的迷宫 ----- P1605
import java.util.Scanner;
public class dfs_01 {
static int next[][] = {{0,1},{1,0},{0,-1},{-1,0}};//此为顺时针四个方向
static int book[][];//标记一个深度中的元素
static int n,m,a[][];//此处避免传参，java中的全局变量需要设置成为静态
static int startx,starty,endx,endy;
static int num = 0;
static void dfs(int x,int y) {
int tx,ty;
if(x == endx && y == endy) {
num++;
return;
}
for(int k=0;k<4;k++) {
tx = x+next[k][0];
ty = y+next[k][1];//下一个点的坐标
if(tx < 0 || tx > n-1 || ty < 0 || ty > m-1) {//判断越界否
continue;
}
if(a[tx][ty] == 0 && book[tx][ty] == 0) {//下一个点若符合条件，就沿着走下去
book[tx][ty] = 1;
dfs(tx,ty);
book[tx][ty] = 0;
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
book = new int[n][m];
a= new int[n][m];
int stopNum = scanner.nextInt(),stop[][] = new int[stopNum][2];//此处记录何处有障碍
startx = scanner.nextInt()-1;
starty = scanner.nextInt()-1;//此处减1,亦可修改地图
endx = scanner.nextInt()-1;
endy = scanner.nextInt()-1;//此处减1,亦可修改地图
int t1 = 0,t2 = 0;
book[startx][starty] = 1;
for(int i=0;i<stopNum;i++) {//此for循环为求出地图
for(int j=0;j<2;j++) {
stop[i][j] = scanner.nextInt()-1;
if(j == 0) {
t1 = stop[i][j];
}
if(j == 1) {
t2 = stop[i][j];
}
}
a[t1][t2] = 1;//若有障碍，地图上标 1
}
dfs(startx,starty); //传入起点，进行深搜
System.out.println(num);
}
}
网友评论