package com.shentu.suanfa;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* 迷宮問題：隊列，廣度優(yōu)先 最短路徑
*
* @author ljx
*/
public class MazeQueue{
? ? public static int[][] arr ={
? ? ? ? ? ? {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
? ? ? ? ? ? {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
? ? ? ? ? ? {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
? ? ? ? ? ? {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
? ? ? ? ? ? {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
? ? ? ? ? ? {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
? ? ? ? ? ? {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
? ? ? ? ? ? {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
? ? ? ? ? ? {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
? ? ? ? ? ? {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
? ? };
? ? /**
* 用于存放路徑頭
*/
? ? public static Queue<Position> queue =new LinkedList<Position>();
? ? /**
* 標記實際數(shù)組中的位置
*/
? ? public static int i =0;
? ? public static void path(int x1, int y1, int x2, int y2) {
? ? ? ? Position position =new Position(x1, y1, -1);
? ? ? ? // 用于存放路徑詳情
? ? ? ? Position[] pos =new Position[arr.length *arr[0].length];
? ? ? ? queue.add(position);
? ? ? ? while (!queue.isEmpty()) {
? ? ? ? ? ? Position poll =queue.poll();
? ? ? ? ? ? pos[i] = poll;
? ? ? ? ? ? // 判斷當前節(jié)點是否是終點
? ? ? ? ? ? if (poll.x == x2 && poll.y == y2) {
? ? ? ? ? ? ? ? // 重新放回去確保最低有一個節(jié)點
? ? ? ? ? ? ? ? queue.offer(poll);
break;
? ? ? ? ? ? }
? ? ? ? ? ? // 向下查找
? ? ? ? ? ? if (arr[poll.x -1][poll.y] ==0) {
? ? ? ? ? ? ? ? // 加入到隊列
? ? ? ? ? ? ? ? queue.offer(new Position(poll.x -1, poll.y, i));
? ? ? ? ? ? ? ? // 標記為走過
? ? ? ? ? ? ? ? arr[poll.x -1][poll.y] =2;
? ? ? ? ? ? }
? ? ? ? ? ? // 向上查找
? ? ? ? ? ? if (arr[poll.x +1][poll.y] ==0) {
? ? ? ? ? ? ? ? // 加入到隊列
? ? ? ? ? ? ? ? queue.offer(new Position(poll.x +1, poll.y, i));
? ? ? ? ? ? ? ? // 標記走過
? ? ? ? ? ? ? ? arr[poll.x +1][poll.y] =2;
? ? ? ? ? ? }
? ? ? ? ? ? // 向右查找
? ? ? ? ? ? if (arr[poll.x][poll.y +1] ==0) {
? ? ? ? ? ? ? ? // 加入隊列
? ? ? ? ? ? ? ? queue.offer(new Position(poll.x, poll.y +1, i));
? ? ? ? ? ? ? ? // 標記走過
? ? ? ? ? ? ? ? arr[poll.x][poll.y +1] =2;
? ? ? ? ? ? }
? ? ? ? ? ? // 向左查找
? ? ? ? ? ? if (arr[poll.x][poll.y -1] ==0) {
? ? ? ? ? ? ? ? // 加入隊列
? ? ? ? ? ? ? ? queue.offer(new Position(poll.x, poll.y -1, i));
? ? ? ? ? ? ? ? // 標記走過
? ? ? ? ? ? ? ? arr[poll.x][poll.y -1] =2;
? ? ? ? ? ? }
? ? ? ? ? ? i++;
? ? ? ? }
? ? ? ? if (queue.isEmpty()) {
? ? ? ? ? ? System.out.println("沒找到路");
? ? ? ? } else {
? ? ? ? ? ? int j =i;
? ? ? ? ? ? Stack<Position> stack =new Stack<Position>();
? ? ? ? ? ? while (pos[j].parent != -1) {
? ? ? ? ? ? ? ? stack.push(pos[j]);
? ? ? ? ? ? ? ? j = pos[j].parent;
? ? ? ? ? ? }
? ? ? ? ? ? stack.push(position);
? ? ? ? ? ? while (!stack.isEmpty()) {
? ? ? ? ? ? ? ? System.out.println(stack.pop().toString());
? ? ? ? ? ? }
}
}
? ? public static void main(String[] args) {
? ? ? ? path(1, 1, 8, 8);
? ? }
? ? public static class Position{
? ? ? ? private int x;
? ? ? ? private int y;
? ? ? ? private int parent;
? ? ? ? Position(int x, int y, int parent) {
? ? ? ? ? ? this.x = x;
? ? ? ? ? ? this.y = y;
? ? ? ? ? ? this.parent = parent;
? ? ? ? }
? ? ? ? @Override
? ? ? ? public StringtoString() {
? ? ? ? ? ? return x +"," +y;
? ? ? ? }
}
}
