迷宫的最短路径

标签: 迷宫 最短路径 | 发表时间:2014-08-19 00:31 | 作者:yangjianzhouctgu
出处:http://www.iteye.com
代码如下:


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


已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [迷宫 最短路径] 推荐:

迷宫的最短路径

- - 编程语言 - ITeye博客
* TODO :给定一个大小为N*M的迷宫,迷宫由通道和墙壁组成,每一步可以向邻接的上下左右四 * 格的通道移动. if (0 <= xp && xp < N && 0 <= yp && yp < M && mazeMatrix[xp][yp] != '#' && distance[xp][yp] == INF) {.

最短路径与贪婪 - Vamei

- - 博客园_首页
作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明. 图是由节点和连接节点的边构成的. 节点之间可以由路径,即边的序列. 根据路径,可以从一点到达另一点. 在一个复杂的图中,图中两点可以存在许多路径. 最短路径讨论了一个非常简单的图论问题,图中从A点到B点 ,那条路径耗费最短.

解析Bellman-Ford算法求最短路径

- - CSDN博客推荐文章
上一篇博文已经说了用dijkstra算法来求图(有向图和无向图)的最短路径了,那么怎么还需要使用Bellman-Ford算法来求解最短路径问题呢. 其实这两个算法有各自求解的限制条件:dijkstra算法不能求解包含负权的图;但是用矩阵来存储图的话,那么Bellman-Ford算法时间复杂度达O(n3),所以这也是一个限制.

外人打不开的迷宫盒子

- Bruce - 果壳网 guokr.com - 果壳网
DIYer:matthewvenn 制作时间:根据你是手工还是机打而定 制作难度:★★★★☆ GEEK指数:★★★★☆. 要想打开它,你就必需采用某种特定手势,并按下一个按钮. 手势是通过内部的滚珠轴承迷宫的形状决定的. 你可以轻松地改变一下迷宫,形成一个只有你自己能够解开的谜题. 在设计中采用了参变量,因此可以轻松地使用不同厚度的材料进行制作.

【每日邮报】宜家“迷宫”的玄机

- Me - article.yeeyan.org
如果您曾经在宜家商场里迷了路,没关系,很多人都有这样的经历. The home furnishing chain’s mazy layouts are a psychological weapon to part shoppers from their cash, an expert in store design claims..

2011年度最变态的迷宫难题

- Dajusha - Matrix67: My Blog
    下面大家将会看到的是一个极其简单而又极其复杂的“迷宫”,这无疑是我在本年度见到的最变态的谜题:从左边入口处的 2011 进去,在迷宫里转悠,最后变成 2012 从右边出来. 你可以在迷宫里转圈,可以重复之前走过的路,但不能往回退着走. 2011 +7 ÷2 +7 ÷2 +7 -5 ×3 ÷2 +7 ÷2 +7 ×3 -5 ÷2 +7 ÷2 +7 -5 ×3 -5 ×3 ÷2 +7 -5 ×3 ÷2 +7 -5 = 2012.