package com.shentu.suanfa;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* 迷宫问题：队列，广度优先 最短路径
*
* @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>();
/**
* 标记实际数组中的位置
*/
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;
// 判断当前节点是否是终点
if (poll.x == x2 && poll.y == y2) {
// 重新放回去确保最低有一个节点
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;
}
}
}
