诡异的楼梯

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 16275 Accepted Submission(s): 4276

Problem Description

Hogwarts正式开学以后,Harry发现在Hogwarts里,某些楼梯并不是静止不动的，相反,他们每隔一分钟就变动一次方向.
比如下面的例子里,一开始楼梯在竖直方向,一分钟以后它移动到了水平方向,再过一分钟它又回到了竖直方向.Harry发现对他来说很难找到能使得他最快到达目的地的路线,这时Ron(Harry最好的朋友)告诉Harry正好有一个魔法道具可以帮助他寻找这样的路线,而那个魔法道具上的咒语,正是由你纂写的.
 
Input
 
测试数据有多组，每组的表述如下：
第一行有两个数,M和N,接下来是一个M行N列的地图,'*'表示障碍物,'.'表示走廊,'|'或者'-'表示一个楼梯,并且标明了它在一开始时所处的位置:'|'表示的楼梯在最开始是竖直方向,'-'表示的楼梯在一开始是水平方向.地图中还有一个'S'是起点,'T'是目标,0<=M,N<=20,地图中不会出现两个相连的梯子.Harry每秒只能停留在'.'或'S'和'T'所标记的格子内.
 
Output
 
只有一行,包含一个数T,表示到达目标的最短时间.
注意:Harry只能每次走到相邻的格子而不能斜走,每移动一次恰好为一分钟,并且Harry登上楼梯并经过楼梯到达对面的整个过程只需要一分钟,Harry从来不在楼梯上停留.并且每次楼梯都恰好在Harry移动完毕以后才改变方向.
 
Sample Input
 
5 5 *..T .. ..|.. ... S....
 
Sample Output
 
7
 
Hint
 
Hint
 
地图如下：

image

Solution

这是一个广度优先搜索问题 其中容易被忽略的一点就是当楼梯不可通过时可以在原地等一秒再通过

Code

package acm1180;
 
/**
 * date:2017.12.7
 * author:孟小德
 * function:    杭电acm1180
 *      诡异的楼梯
 */
 
import java.util.*;
 
class Node
{
    int row,column,time;
    public Node(int row,int column,int time)
    {
        this.row = row;
        this.column = column;
        this.time = time;
    }
    public Node(int row,int column)
    {
        this.row = row;
        this.column = column;
    }
}
 
public class Main
{
    public static int[][] map;
    public static boolean[][] visit;
    public static int M,N,time;
    public static Node S,T;
    public static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
    // public static int flag;     //记录前一次的方向
 
    public static boolean crossBorder(int r,int c)
    {
        if (r < 1 || c < 1 || r > M || c > N)
        {
            return true;
        }
        else if (map[r][c] == 0 || visit[r][c] == true)
        {
            return true;
        }
        return false;
    }
 
    public static void BFS()
    {
        Queue<Node> nodeQ = new LinkedList<Node>();
        nodeQ.add(S);
        while (!nodeQ.isEmpty())
        {
            Node curNode = nodeQ.poll();
            if ((curNode.row == T.row) && (curNode.column == T.column))
            {
                if (curNode.time < time)
                {
                    time = curNode.time;
                }
            }
            for (int i = 0;i<4;i++)
            {
 
                int r = curNode.row + dir[i][0];
                int c = curNode.column + dir[i][1];
                visit[curNode.row][curNode.column] = true;
                if (!crossBorder(r,c))
                {
                    Node temp;
                    if (map[r][c] == 1)
                    {
 
                        temp = new Node(r,c,curNode.time+1);
                        nodeQ.add(temp);
                    }
                    else
                    {
                        while ((curNode.time + i + map[r][c]) % 2 == 0)
                        {
                            curNode.time++;
                        }
                        r += dir[i][0];
                        c += dir[i][1];
                        if (!crossBorder(r,c))
                        {
                            temp = new Node(r,c,curNode.time+1);
                            nodeQ.add(temp);
                        }
                        curNode.time--;
                    }
                }
 
            }
        }
    }
 
 
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
 
        while (input.hasNextInt())
        {
            M = input.nextInt();    //地图行
            N = input.nextInt();    //地图列
            map = new int[M+1][N+1];    //地图信息
            visit = new boolean[M+1][N+1];  //节点是否访问过
 
            input.nextLine();
 
            // 输入
            for (int i=0;i<M;i++)
            {
                String str = input.nextLine();
                char c;
                for (int j=0;j<N;j++)
                {
                    c = str.charAt(j);
                    switch (c)
                    {
                        case '*':
                            map[i+1][j+1] = 0;
                            visit[i+1][j+1] = true;
                            break;
                        case '.':
                            map[i+1][j+1] = 1;
                            visit[i+1][j+1] = false;
                            break;
                        case '-':
                            map[i+1][j+1] = -2;     //时间加上此处的值对2取模，
                            visit[i+1][j+1] = false;
                            break;
                        case '|':
                            map[i+1][j+1] = -1;     //若值为1则楼梯竖，否则横
                            visit[i+1][j+1] = false;
                            break;
                        case 'S':
                            map[i+1][j+1] = 1;
                            visit[i+1][j+1] = false;
                            S = new Node(i+1,j+1,0);
                            break;
                        case 'T':
                            map[i+1][j+1] = 1;
                            visit[i+1][j+1] = false;
                            T = new Node(i+1,j+1);
                            break;
                    }
 
                }
            }
 
            time = 100;
            
            BFS();
            System.out.println(time);
        }
    }
}