DFS BFS回顾

前言：这次回顾用一道简单的BFS，DFS入门题目进行。其实一年之前就学习过DFS,BFS,并且用C++ AC了这一道题目，当时初学时的自己在AC过后，兴奋之余也没想着要经常温习回顾，这也是导致今天再次做到这道题时，磕磕绊绊，思前想后，敲代码时犹豫不决的原因之一；这也鞭策我要经常温习之前学过的知识。

话不多说，先上题：（题目来自HNUCM）

题目描述

小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。小明只能向上下左右四个方向移动

输入

输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。每组输入的第一行是两个整数N和M（1<=N,M<=100）。接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。字符的含义如下： ‘S’：起点 ‘E’：终点 ‘-’：空地，可以通过 ‘#’：障碍，无法通过输入数据保证有且仅有一个起点和终点。

输出

对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。

样例输入

1
5 5
S-###
-----
##---
E#---
---##

样例输出

这次我用Java对这道题进行回顾

首先上DFS（一条路走到黑）,这种用时间换取空间的做法大多会TLE,事实也确实如此，这道题可以用DFS解出来，但是会超时，因为反复的递归耗费了大量的时间。

DFS code:

import java.util.Queue;
import java.util.Scanner;

public class HNUCM_1221_DFS {
    public static int p,q;

    //存放地图的数组
    public static char[][] arr;

    //标记数组
    public static int[][] maker;

    public static int sx,sy,gx,gy;

    //初始化最短值
    public static int min = 99999;

    public static int[] dx = {1,0,-1,0};
    public static int[] dy = {0,1,0,-1};

    public static void dfs(int x,int y,int step){
        //到达终点
        if (x==gx && y==gy){
            if (step < min){
                min = step;
            }
            return;
        }
        //向四个方向走
        for (int i = 0; i < 4 ;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            //判断有没有出界，如果出界退出此次循环
            if (nx > p-1 || nx < 0 || ny > q-1 || ny < 0){
                continue;
            }

            //判断有没有碰壁
            if (arr[nx][ny] != '#' && maker[nx][ny] == 0){
//                System.out.println(nx+" "+ny);
                //标记走过
                maker[nx][ny] = 1;
                dfs(nx,ny,step+1);
                //取消标记
                maker[nx][ny] = 0;
            }
        }
        return;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);


        int n = sc.nextInt();

        while (n-->0){
            p = sc.nextInt();
            q = sc.nextInt();

            arr = new char[p][q];
            maker = new int[p][q];
            //初始化迷宫
            for (int i = 0 ;i < p ;i++){
                String b = sc.next();
                for (int j = 0 ; j < q ;j++){
                    arr[i][j] = b.charAt(j);
                    //确定起点，终点坐标
                    if (arr[i][j] == 'S'){
                        sx = i;
                        sy = j;
                    }
                    if (arr[i][j] == 'E'){
                        gx = i;
                        gy = j;
                    }
                }
            }

            dfs(sx,sy,0);

//            System.out.println(sx+" "+sy);
            if (min == 99999){
                min = -1;
            }

            System.out.println(min);
            min = 99999;
        }
    }
}

BFS code:

import java.util.LinkedList;
import java.util.Scanner;

public class HNUCM_1221_BFS {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int min = 99999;

        //方向数组
        int[] dx = {1,0,-1,0};
        int[] dy = {0,1,0,-1};

        //输入数据组数
        int n = sc.nextInt();


        while (n-- > 0) {
            int p = sc.nextInt();
            int q = sc.nextInt();

            char[][] map = new char[p][q];
            int sx = 0,sy = 0,gx = 0,gy = 0;
            //初始化地图
            for (int i = 0 ; i < p ;++i){
                String a = sc.next();
                for (int j = 0 ;j < q ; ++j){
                    map[i][j] = a.charAt(j);
                    if (map[i][j] == 'S') {
                        sx = i;
                        sy = j;
                    }
                    if (map[i][j] == 'E') {
                        gx = i;
                        gy = j;
                    }
                }
            }
            Node start = new Node(sx,sy,null);
            //创建队列，BFS准备工作
            LinkedList<Node> queue = new LinkedList<>();
            //创建临时节点
            Node tmp = null;
            //压入开始节点
            queue.offer(start);
            //开始bfs搜素地图
            ok:
            while (!queue.isEmpty()) {
                //出队第一个节点
                tmp = queue.poll();
                //遍历四个方向
                for (int i = 0 ; i < 4;++i){
                    int nx = tmp.x + dx[i];
                    int ny = tmp.y + dy[i];
                    //看是否超出边界
                    if (nx < 0 || nx > p-1 || ny < 0 || ny > q-1) {
                        continue;
                    }
                    if (map[nx][ny] == '#') {
                        continue;
                    }
                    Node next = new Node(nx,ny,tmp);
                    //找到终点
                    if (nx == gx && ny == gy) {
//                        min = next.dis-1;
                        queue.clear();
                        queue.offerFirst(next);
                        Node preNode = next.pre;
                        while (preNode != null) {
                            queue.offerFirst(preNode);
                            preNode = preNode.pre;
                        }
                        min = queue.size();
                        System.out.println(min-1);
                        break ok;
                    }
                    map[nx][ny] = '#';
                    queue.offer(next);
                }
            }
            if (min == 99999){
                System.out.println(-1);
            }
            //这是个坑！！！我第一次把他写在了外面，以至于一直报WA50%
            min = 99999;

        }
    }

}
class Node{
    int x;
    int y;
    int dis;
    Node pre;
    public Node(int x,int y,Node N){
        this.x = x;
        this.y = y;
        this.pre = N;
    }

}

「真诚赞赏，手留余香」

DFS BFS回顾

TOC

DFS BFS回顾

DFS code:

BFS code:

FEATURED TAGS

FRIENDS