package myalgorithm;

import java.util.Arrays;

import java.util.LinkedList;

import java.util.Queue;

/*BFS用于记录的位置和值的结构*/

class node

{

    node(int xparam,int yparam,int valparam)

    {

        this.x = xparam;

        this.y = yparam;

        this.value = valparam;

    }

    int x,y,value;

}

public class ShortPath {

    /*全局最短路径*/

    public int stepnum = 999;

    /*构建11*11的迷宫,英雄H在(1,1)的位置出发，去解救美女M(6,8)*/

    char[][] graph = {

            {'#','#','#','#','#','#','#','#','#','#','#'},

            {'#','H','_','_','*','_','_','*','_','_','#'},

            {'#','_','_','_','_','_','_','_','_','_','#'},

            {'#','_','*','_','_','_','*','_','_','_','#'},

            {'#','_','_','_','*','_','_','_','_','*','#'},

            {'#','_','_','_','_','_','_','*','_','*','#'},

            {'#','_','*','_','_','_','_','_','M','_','#'},

            {'#','*','_','_','*','_','_','_','_','_','#'},

            {'#','_','_','_','_','_','_','_','_','_','#'},

            {'#','_','_','_','*','_','_','_','_','_','#'},

            {'#','#','#','#','#','#','#','#','#','#','#'},

    };

    /*初始标记数组都为0*/

    public int[][] mark = new int[graph.length][graph.length];

    /*每一个位置有四种选择：右下左上*/

    public int[][] choose = {

            {0,1},

            {1,0},

            {0,-1},

            {-1,0}

    };

  /*BFS算法*/

    public void BFS(node startPoint)

    {

        //起始点装入队列

        Queue<node> queue = new LinkedList<node>();

        startPoint.value = 1;//确保起始步数为1

        queue.offer(startPoint);

        node t1;

        int tx,ty;

        top:

        while(!queue.isEmpty())

        {

            //取队首，出队后不再入队，value也自此固定

            t1 = queue.poll();

            mark[t1.x][t1.y] = t1.value;//标记步数

            for(int i=0;i<4;i++)

            {

                tx = t1.x + choose[i][0];

                ty = t1.y + choose[i][1];

                //找到美女，肯定是最短的，可以立即返回

                if(graph[tx][ty] == 'M')

                {

                    stepnum = t1.value + 1;//下一步可到

                    mark[tx][ty] = stepnum;

                    break top;

                }

                //继续接着找，把空路径添加到队列末尾

                //不是炸弹和围墙,并且没有被标记

                if(graph[tx][ty] != '#'

                        && graph[tx][ty] != '*'

                        &&mark[tx][ty] == 0)

                {

                    queue.offer(new node(tx,ty,t1.value+1));

                }

            }

        }

    }

    /*BFS回溯路径*/

    private void getPath(node target) {

        int beforex = 0,beforey = 0;

        int x = target.x;

        int y = target.y;

        for(int i=0;i<4;i++)

        {

            beforex = x + choose[i][0];

            beforey = y + choose[i][1];

            //找到英雄的出发点，函数结束

            if (beforex == 1 && beforey == 1)

            {

                return;

            }

            if(mark[x][y] - 1 == mark[beforex][beforey])

            {

                System.out.print("("+beforex+","+beforey+")<--");

                break;

            }

        }

        getPath(new node(beforex,beforey,0));

        return;

    }
    /*main函数*/

    public static void main(String[] args) {

        ShortPath my = new ShortPath();

        long start = System.currentTimeMillis();

        my.BFS(new node(1,1,0));

        long end = System.currentTimeMillis();

        System.out.println("BFS step: " + my.stepnum + " time:" + (end-start));

        //打印标记结果

        for (int m = 0;m<my.graph.length;m++)

            System.out.println(Arrays.toString(my.mark[m]));

        //打印巡回路径

        my.getPath(new node(6,8,0));

    }

}