BFS解决迷宫问题

1462463343

听说这个月是蓝桥杯的决赛，嗯，所以我又要临时抱佛脚了

这两天练习BFS广度优先搜索算法，看了一下算法思想，没错就是它http://rapheal.iteye.com/blog/1526861

按我来理解其实就跟DFS深度探索差不多，都是遍历，深度是无限的往下遍历，广度是寻找可通行的路径

嗯是的，BFS、很重要的一个算法，可以使用栈的先进后出或者队列的先进先出思想来解决。

然后我水了一题简单而典型的迷宫问题

题目出自：hncu ACM练习1102
题目描述

小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。

小明只能向上下左右四个方向移动。
输入格式

输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。

每组输入的第一行是两个整数N和M（1<=N,M<=100）。

接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。

字符的含义如下：

‘S’：起点

‘E’：终点

‘-’：空地，可以通过

‘#’：障碍，无法通过

输入数据保证有且仅有一个起点和终点。
输出

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

public class SimpleBFS {

class Node {
    int x, y, step;

    Node() {
    }

    Node(int x, int y, int step) {
        this.x = x;
        this.y = y;
        this.step = step;
    }
}

static char map[][] = new char[105][105];
static int vis[][] = new int[105][105]; // 标记探索过的位置
static int dir[][] = new int[][] { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }; // 探索规则
static int n, m, sx, sy, ans;

// 检查是否越界符合规则
static boolean judge(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m)
        return true;
    if (vis[x][y] == 1 || map[x][y] == '#')
        return true;
    return false;
}

static void bfs() {
    int i;
    Queue<Node> Q = new LinkedList<Node>();
    SimpleBFS bfs = new SimpleBFS();
    Node a = bfs.new Node();
    Node next = bfs.new Node();
    Node top = bfs.new Node();
    a.x = sx;
    a.y = sy;
    a.step = 0;
    vis[a.x][a.y] = 1;
    Q.offer(a);
    while (!Q.isEmpty()) {
        top = Q.poll(); // 出列
        if (map[top.x][top.y] == 'E') {
            ans = top.step;
            return;
        }
        for (i = 0; i < 4; i++) {
            next = top;
            next.x += dir[i][0];
            next.y += dir[i][1];
            if (judge(next.x, next.y))
                continue;
            next.step = top.step + 1;
            vis[next.x][next.y] = 1; // 标记已探索的位置
            Q.offer(bfs.new Node(next.x, next.y, next.step)); // 入列
        }
    }
    ans = -1;
}

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

    n = scanner.nextInt();
    m = scanner.nextInt();
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            map[i][j] = scanner.next().charAt(0);
    // 找到开始位置
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) {
            if (map[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    bfs();
    System.out.println("最短路径:" + ans);

    scanner.close();
}

}

运行结果

通过

解题反馈

嗯，不得不说，解题时候遇到一个很无解的问题，算法是没问题的，我还特意用C语言写了一遍，对，算法确实没问题，结果是可以出来的，但是没问题就是最大的问题。

一次又一次的测试，起码10次，当然过程会很烦躁，跑完步回来的我灵机一动，天大的问题出现了。

问题在入列这一行，当时我是这样写的

Q.offer(next); // 入列

我天，经过我测试，真是我错了，Queue测试

测试代码

public class QueueTest {

class Node {
    int x, y, step;

    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    Node() {
    }
}

public static void main(String[] args) {
    // TODO Auto-generated method stub

    Queue<Node> queueQ = new LinkedList<Node>();
    QueueTest queueTest = new QueueTest();
    queueQ.offer(queueTest.new Node(1, 1));
    queueQ.offer(queueTest.new Node(2, 2));
    queueQ.offer(queueTest.new Node(3, 3));
    queueQ.offer(queueTest.new Node(4, 4));
    System.out.println("--当前队列--");
    for (Node q : queueQ) {
        System.out.println("x:" + q.x + "--y:" + q.y);
    }
    Node a = queueQ.poll();
    System.out.println("poll=>" + "x:" + a.x + "--y:" + a.y); // 返回第一个元素，并在队列中删除
    System.out.println("--删除顶部后的队列--");
    for (Node q : queueQ) {
        System.out.println("x:" + q.x + "--y:" + q.y);
    }
    System.out.println("--添加一个元素后的当前队列--");
    queueQ.offer(queueTest.new Node(99, 99));
    for (Node q : queueQ) {
        System.out.println("x:" + q.x + "--y:" + q.y);
    }
    System.out.println("--添加一个元素后的队列--");
    Node Ape = queueTest.new Node();
    Ape.x = 88;
    Ape.y = 88;
    queueQ.offer(Ape);
    for (Node q : queueQ) {
        System.out.println("x:" + q.x + "--y:" + q.y);
    }
    System.out.println("--添加一个原有对象的元素后的队列--");
    Ape.x = 881;
    Ape.y = 881;
    queueQ.offer(Ape);
    for (Node q : queueQ) {
        System.out.println("x:" + q.x + "--y:" + q.y);
    }

}

}

运行结果

–当前队列–
x:1–y:1
x:2–y:2
x:3–y:3
x:4–y:4
poll=>x:1–y:1
–删除顶部后的队列–
x:2–y:2
x:3–y:3
x:4–y:4
–添加一个元素后的当前队列–
x:2–y:2
x:3–y:3
x:4–y:4
x:99–y:99
–添加一个元素后的队列–
x:2–y:2
x:3–y:3
x:4–y:4
x:99–y:99
x:88–y:88
–添加一个原有对象的元素后的队列–
x:2–y:2
x:3–y:3
x:4–y:4
x:99–y:99
x:881–y:881
x:881–y:881

我能说什么