BFS(G, s)    
        init V[G]   // 由测试用例实现。
        status[s] = S    // s王子的位置，通过一次遍历可以获取其坐标。
        
        int count = -1;
        queue q
        q.add(s) // 将王子的位置入队。
        while !q.isEmpty()
            t = q.poll()
            for each vertex v in Adj[t] // 与t邻接的点
                if status[v] = 'P'    // 只对未访问的操作
                    count = step[v] = step[t] + 1
                    q.clear()
                    break
                elseif status[v] = '.'    
                    status[v] = '#'    // 标记为已经走过该节点
                    q.add(v)
                    step[v] = step[t] + 1 // 累加得到当前节点的步长
                elseif status[v] = '*'
                    step[v] = -1   // 遇到墙，则将该节点的距离置为-1，在遍历完整个图时，
                                   // 如果遇到最后一个节点的值为-1，则表明没有找到。
                else
                    error
                
        if count != -1
            if count < L
                return true
        return false

package com;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    /**
     * 公主被魔王抓走了，王子需要拯救出美丽的公主。他进入了魔王的城堡，魔王的城堡是一座很大的迷宫。
     * 为了使问题简单化，我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙，王子不能通过。王子只
     * 能移动到相邻(上下左右四个方向)的方格内，并且一秒只能移动一步。地图由'S'，'P'，'.'，'*'
     * 四种符号构成，'.'表示王子可以通过，'*'表示墙，王子不能通过；'S'表示王子的位置；'P'表示公主
     * 的位置；T表示公主存活的剩余时间，王子必须在T秒内到达公主的位置，才能救活公主。如下图所示：
     */
    public class SavePrincess
    {
        private int m;
        private int n;
        private char[][] visited;
        private Position s = null;
        private Position p = null;
        public static void main(String[] args)
        {
            char maze[][] = {
            /* 0 1 2 3 4 5 6 7 8 9 */
            /* 0 */{ '.', '*', '.', '.', '.', '*', '.', '.', '.', '.' },
            /* 1 */{ '*', 'S', '*', '.', '.', '.', '.', '.', '.', '.' },
            /* 2 */{ '.', '*', '*', '.', '.', '.', '.', '.', '.', '.' },
            /* 3 */{ '.', '.', '*', '*', '*', '.', '.', '.', '.', '.' },
            /* 4 */{ '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
            /* 5 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },
            /* 6 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },
            /* 7 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },
            /* 8 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },
            /* 9 */{ '.', 'P', '.', '.', '*', '.', '.', '.', '.', '.' } };
            new SavePrincess().saved(maze, 10, 8, 11);
        }
        /**
         * @param vis
         *            M行N列迷宫
         * @param m
         *            M
         * @param n
         *            N
         * @param t
         *            T
         * 
         * @return boolean true表示营救成功，反之表示失败。
         */
        public boolean saved(char[][] vis, int m, int n, int t)
        {
            if (t < 0)
            {
                return false;
            }
            this.m = m;
            this.n = n;
            this.visited = vis;
            int step[][] = new int[m][n];
            init(m, n, step);
            if (s == null || p == null)
            {
                System.out.println("input visited error!");
                return false;
            }
            Queue<Position> queue = new LinkedList<Position>();
            queue.add(s);
            int l = -1;
            while (!queue.isEmpty())
            {
                Position e = queue.poll();
                l = dealOneNode(step, queue, l, e);
            }
            if (l != -1 && l <= t)
            {
                System.out.println("Saved the princess in " + l + " seconds!");
                return true;
            }
            System.out.println("failed saved the princess! " + l + " > " + "t");
            return false;
        }
        private void init(int m, int n, int[][] step)
        {
            for (int i = 0; i != m; i++)
            {
                for (int j = 0; j != n; j++)
                {
                    System.out.print(visited[i][j]);
                    System.out.print(' ');
                    step[i][j] = 0;
                    switch (visited[i][j])
                    {
                    case '*':
                        break;
                    case 'S':
                        this.s = new Position(i, j, 'S');
                        break;
                    case '.':
                        break;
                    case 'P':
                        this.p = new Position(i, j, 'P');
                        break;
                    default:
                        System.out.println("input visited error!");
                        System.exit(-1);
                    }
                }
                System.out.println("");
            }
        }
        private int dealOneNode(int[][] step, Queue<Position> queue, int l, Position e)
        {
            /**
             * 在求相邻节点时做了一点优化，遇到墙的节点则不放到相邻节点中。
             * 从设计思想和可读性上看不是太好，从运行效率考虑，可以。
             */
            for (Position c : getNextPostions(e))
            {
                switch (c.getV())
                {
                case 'P':
                    queue.clear();
                    l = step[e.getI()][e.getJ()] + 1;
                    break;
                case '.':
                    visited[c.getI()][c.getJ()] = '#';
                    queue.add(c);
                    step[c.getI()][c.getJ()] = step[e.getI()][e.getJ()] + 1;
                    break;
                default:
                    // 不可能进入该分支。
                    System.err.println("some error!");
                    break;
                }
            }
            return l;
        }
        /**
         * 取有效节点。
         * 遇到墙则不加入相邻节点中。
         * 
         * @param e
         * @return
         */
        private List<Position> getNextPostions(Position e)
        {
            int i = e.getI();
            int j = e.getJ();
            List<Position> lst1 = new LinkedList<Position>();
            addOneNode(i + 1, j, lst1);
            addOneNode(i, j + 1, lst1);
            addOneNode(i - 1, j, lst1);
            addOneNode(i, j - 1, lst1);
            return lst1;
        }
        private void addOneNode(int i, int j, List<Position> lst)
        {
            if (i >= m || i < 0 || j >= n || j < 0)
            {
                return;
            }
            char v = visited[i][j];
            switch (v)
            {
            case '.':
            case 'P':
                lst.add(new Position(i, j, v));
                break;
            default:
                break;
            }
        }
        private class Position
        {
            private int i;
            private int j;
            private char v;
            public Position(int i, int j, char value)
            {
                this.i = i;
                this.j = j;
                this.v = value;
            }
            public char getV()
            {
                return v;
            }
            public int getI()
            {
                return i;
            }
            public int getJ()
            {
                return j;
            }
            public String toString()
            {
                return "(" + i + ", " + j + ")";
            }
        }
    }