迷宫营救公主算法

package com;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 公主被魔王抓走了，王子需要拯救出美丽的公主。他进入了魔王的城堡，魔王的城堡是一座很大的迷宫。
 * 为了使问题简单化，我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙，王子不能通过。王子只
 * 能移动到相邻（上下左右四个方向)的方格内，并且一秒只能移动一步。地图由'S'，'P'，'.'，'*'
 * 四种符号构成，'.'表示王子可以通过，'*'表示墙，王子不能通过；'S'表示王子的位置；'P'表示公主
 * 的位置；T表示公主存活的剩余时间，王子必须在T秒内到达公主的位置，才能救活公主。如下图所示：
 */
public class SavePrincess
{
    private int m;
    private int n;
    private char[][] visited;
    private Map<Position, List<Position>> data = new HashMap<Position, List<Position>>();
    private int t;
    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', '.', '*', '.', '.', '.', '.', '.' } };

        // 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)
    {
        this.m = m;
        this.n = n;
        this.visited = vis;
        this.t = t;

        for (int i = 0; i != m; i++)
        {
            for (int j = 0; j != n; j++)
            {
                System.out.print(visited[i][j]);
                System.out.print(' ');
                Position tmp = new Position(i, j);
                switch (visited[i][j])
                {
                case '*':
                    break;
                case 'S':
                    this.s = tmp;
                    break;
                case '.':
                    prepareNode(i, j, tmp);
                    break;
                case 'P':
                    this.p = tmp;
                    prepareNode(i, j, tmp);
                default:
                    break;
                }
            }
            System.out.println("");
        }

        if (s == null || p == null)
        {
            System.out.println("input visited error!");
            return false;
        }

        Set<Position> excudedNode = new HashSet<Position>();
        int l = findNearstWay(p, excudedNode);

        if (l < 0)
        {
            System.out.println("failed saved the princess!");
            return false;
        }
        else
        {
            System.out.println("Saved the princess in " + l + " seconds!");
            return true;
        }

    }

    private int findNearstWay(Position p2, Set<Position> excudedNode)
    {
        if (s.equals(p2))
        {
            return 0;
        }

        
        List<Position> lst = data.get(p2);
        excudedNode.add(p2);

        int minLen = -1;
        if (lst == null)
        {
            return minLen;
        }
        for (Position o : lst)
        {
            if (excudedNode.contains(o))
            {
                continue;
            }
            
            int len = findNearstWay(o, excudedNode);
            
            if ((len <= this.t && len != -1) && (minLen == -1 || (minLen != -1 && len < minLen)))
            {
                minLen = len;
            }
        }

        excudedNode.remove(p2);
        if (minLen != -1)
        {
            return minLen + 1;
        }
        else
        {
            return minLen;
        }
    }

    private void prepareNode(int i, int j, Position tmp)
    {
        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);
        if (!lst1.isEmpty())
        {
            data.put(tmp, lst1);
        }
    }

    private void addOneNode(int i, int j, List<Position> lst)
    {
        if (i >= m || i < 0 || j >= n || j < 0)
        {
            return;
        }

        switch (visited[i][j])
        {
        case '.':
        case 'S':
            lst.add(new Position(i, j));
            break;
        default:
            break;
        }
    }
}

package com;

public class Position implements Comparable<Position>
{
    private int i;
    private int j;

    public Position(int i, int j)
    {
        this.i = i;
        this.j = j;
    }

    @Override
    public int compareTo(Position o)
    {
        if (this.i == o.i && this.j == o.j)
        {
            return 0;
        }
        else if (this.i > o.i)
        {
            return 1;
        }
        else
        {
            if (this.i > o.j)
            {
                return 1;
            }
            else
            {
                return -1;
            }
        }
    }

    public boolean equals(Object o)
    {
        if (!(o instanceof Position))
        {
            return false;
        }

        if (this.compareTo((Position) o) == 0)
        {
            return true;
        }

        return false;
    }

    public int hashCode()
    {
        int result = 17;
        result = 31 * result + i;
        result = 31 * result + j;
        return result;
    }

    public String toString()
    {
        return "(" + i + ", " + j + ")";
    }
}