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