杭电acm1180|杭电acm1180 诡异的楼梯
诡异的楼梯
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)Problem Description
Total Submission(s): 16275 Accepted Submission(s): 4276
Hogwarts正式开学以后,Harry发现在Hogwarts里,某些楼梯并不是静止不动的，相反,他们每隔一分钟就变动一次方向.Solution
比如下面的例子里,一开始楼梯在竖直方向,一分钟以后它移动到了水平方向,再过一分钟它又回到了竖直方向.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
【杭电acm1180|杭电acm1180 诡异的楼梯】这是一个广度优先搜索问题 其中容易被忽略的一点就是当楼梯不可通过时可以在原地等一秒再通过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 nodeQ = new LinkedList();
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 推荐阅读
- 杭电oj——2030汉字统计
- 那个涵洞很诡异
- [博客搬家]多年前的拙作（《诡异不是我的表现手段|[博客搬家]多年前的拙作：《诡异不是我的表现手段,诡异,就是我本格－诸星大二郎》）
- 比赛题解|2020 杭电多校9 1007 Game （平衡树）
- 2020杭电多校第八场 1008 Hexagon
- 迷雾:诡异的同学会
- HDU 6857 Clockwise or Counterclockwise（2020杭电暑期多校训练第八场）
- 单调栈|2020杭电多校第一场（解题报告）
- 最短路径|2020杭电多校第四场 解题报告1002 1004 1005 1011
- 软硬件集成|调试STM32 串口时的 诡异现象