迷宫的最短路径

代码如下：

package com.chapterOne.exercise;

import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * Created by yangjianzhou on 2014/8/18 21:36.
 * TODO :给定一个大小为N*M的迷宫，迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四
 * 格的通道移动。求从起点到终点所需的最小步数。
 */
public class Maze {

    private static final int INF = 100000;
    private static final int N = 10;
    private static final int M = 10;
    private static char[][] mazeMatrix = {
            {'#', 'S', '#', '#', '#', '#', '#', '#', 'o', '#'},
            {'o', 'o', 'o', 'o', 'o', 'o', '#', 'o', 'o', '#'},
            {'o', '#', 'o', '#', '#', 'o', '#', '#', 'o', '#'},
            {'o', '#', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o'},
            {'#', '#', 'o', '#', '#', 'o', '#', '#', '#', '#'},
            {'o', 'o', 'o', 'o', '#', 'o', 'o', 'o', 'o', '#'},
            {'#', '#', '#', '#', '#', '#', '#', '#', 'o', '#'},
            {'o', 'o', 'o', '#', 'o', 'o', 'o', 'o', 'o', 'o'},
            {'o', '#', '#', '#', '#', 'o', '#', '#', '#', 'o'},
            {'o', 'o', 'o', 'o', '#', 'o', 'o', 'o', 'G', '#'}
    };
    ;
    private static int xs = 0;
    private static int ys = 1;
    private static int xe = 9;
    private static int ye = 8;
    private static int[][] distance = new int[N][M];

    private static int[] xd = {1, 0, -1, 0};
    private static int[] yd = {0, 1, 0, -1};

    public static void main(String[] args) {
        initDistance();
        Maze maze = new Maze();
        int dis = maze.bfs();
        System.out.println("shortest length is : " + dis);
        printDistance();
    }

    private int bfs() {
        Queue<Point> que = new ConcurrentLinkedQueue<Point>();
        que.add(new Point(xs, ys));
        distance[xs][ys] = 0;
        while (que.size() > 0) {
            Point point = que.poll();
            if (point.getX() == xe && point.getY() == ye) {
                break;
            }
            for (int i = 0; i < 4; i++) {
                int xp = point.getX() + xd[i];
                int yp = point.getY() + yd[i];
                if (0 <= xp && xp < N && 0 <= yp && yp < M && mazeMatrix[xp][yp] != '#' && distance[xp][yp] == INF) {
                    que.add(new Point(xp, yp));
                    distance[xp][yp] = distance[point.getX()][point.getY()] + 1;
                }
            }
        }
        return distance[xe][ye];
    }

    private static void initDistance() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                distance[i][j] = INF;
            }
        }
    }

    private static void printDistance() {
        for (int i = 0; i < N; i++) {
            System.out.println();
            for (int j = 0; j < M; j++) {
                System.out.print("\t\t" + distance[i][j]);
            }
        }
    }

    class Point {
        int x;
        int y;

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public void setX(int x) {
            this.x = x;
        }

        public void setY(int y) {
            this.y = y;
        }
    }
}

运行结果如下：

shortest length is : 22

		100000	0		100000	100000	100000	100000	100000	100000	13		100000
		2		1		2		3		4		5		100000	13		12		100000
		3		100000	3		100000	100000	6		100000	100000	11		100000
		4		100000	4		5		6		7		8		9		10		11
		100000	100000	5		100000	100000	8		100000	100000	100000	100000
		8		7		6		7		100000	9		10		11		12		100000
		100000	100000	100000	100000	100000	100000	100000	100000	13		100000
		100000	100000	100000	100000	18		17		16		15		14		15
		100000	100000	100000	100000	100000	18		100000	100000	100000	16
		100000	100000	100000	100000	100000	19		20		21		22		100000