杭电1180java实现（bfs）

诡异的楼梯：
多组数据输入M N,表示大小然后输入地图。*表示墙壁，’.‘表示可以通过，S初始，T结尾位置，‘-’，‘|’代表初始楼梯状况，每隔一秒就会换成对方。-左右走，跳过楼梯，|上下走，跳过楼梯（相当于走两格）
分析：
1：首先要确定上下 和左右的参数设置，不能搞混，我选择a[x][y],x代表上下（行）
2：找到时间最短的点，说明是bfs，并且为了防止爆内存，还要标记走过的路，楼梯不标记，标记过的位置不在走。用的队列还要用优先队列优化
3：难点是’-'和‘|’的处理。因为每秒都会变一次，所以可以要看时间，time%2=0；表示遇到的就是原始的楼梯，time%2=1，代表遇到的是相反的楼梯。
4：难点2就是停留的问题，普通的路是不会停留的，只有遇到楼梯才可能停留，这就是遇到的楼梯过不去的状况，就要判断过去会不会越界，过去的那个点是否已经走过。只有满足条件，对面的点没去过，才会等一次。
附上代码：

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class 杭电1180 {
	static int x[]={0,1,0,-1};
	static int y[]={1,0,-1,0};//右 上 做 下 
	static int m,n; static int x1=0,y1=0,x2=0,y2=0;//起点和抹点
	static char a[][]=new char[20][20];
	public static void main(String[] args) { Scanner sc=new Scanner(System.in); while(sc.hasNext()) { m=sc.nextInt();//行  n=sc.nextInt();//列  sc.nextLine(); boolean b[][]=new boolean[m][n];//标记是否被走过  for(int i=0;i q1=new PriorityQueue(timecomepare2);	//优先队列优化 
	 q1.add(new zuobiao(x1,y1,0));
	 while(!q1.isEmpty())
	 { zuobiao zuo=q1.poll();//取头并且抛出 int x3=zuo.x;int y3=zuo.y; if(x3==x2&&y3==y2) {System.out.println(zuo.time);break;} else for(int i=0;i<4;i ) { if(x3 x[i]=0&&y3 y[i]=0&&!b[x3 x[i]][y3 y[i]])	//这个点没有访问过  { if(a[x3 x[i]][y3 y[i]]=='.')//普通情况，不考虑楼梯 { b[x3 x[i]][y3 y[i]]=true; q1.add(new zuobiao(x3 x[i],y3 y[i],zuo.time 1)); } /* * 遇到竖直楼梯，1：上下方向的偶时间可行 * 2：左右方向的奇时间可行 */ if(a[x3 x[i]][y3 y[i]]=='|')//竖直楼梯 要看时间 { if(zuo.time%2==1&&(i==0||i==2))//奇数时间 相当于‘-’；  { if(y3 y[i] y[i]=0) { b[x3 x[i] x[i]][y3 y[i] y[i]]=true; q1.add(new zuobiao(x3 x[i] x[i],y3 y[i] y[i],zuo.time 1));} } else if(zuo.time%2==0&&(i==1||i==3))//偶数时间	上下  { if(x3 x[i] x[i]=0) {		 b[x3 x[i] x[i]][y3 y[i] y[i]]=true; q1.add(new zuobiao(x3 x[i] x[i],y3 y[i] y[i],zuo.time 1)); } } else if(y3 y[i] y[i]=0&&x3 x[i] x[i]=0) {//没爬过去并且符合条件
	if(b[x3 x[i] x[i]][y3 y[i] y[i]]==false)q1.add(new zuobiao(x3,y3,zuo.time 1));}//并且没有被爬过一定要看看是否被爬过，内存卡爆 } /* * 遇到-方向 1：偶数时间左右方向 * 2：奇数时间的上下方向 */ if(a[x3 x[i]][y3 y[i]]=='-')//竖直楼梯只能左右走，走两步 { if(zuo.time%2==1&&(i==1||i==3))//左右 { if(x3 x[i] x[i]=0) {		 b[x3 x[i] x[i]][y3 y[i] y[i]]=true; q1.add(new zuobiao(x3 x[i] x[i],y3 y[i] y[i],zuo.time 1)); } } else if(zuo.time%2==0&&(i==0||i==2))//偶数时间  { if(y3 y[i] y[i]=0)//符合条件（可以跳过去） {		 b[x3 x[i] x[i]][y3 y[i] y[i]]=true; q1.add(new zuobiao(x3 x[i] x[i],y3 y[i] y[i],zuo.time 1)); } } else if(y3 y[i] y[i]=0&&x3 x[i] x[i]=0) {if(b[x3 x[i] x[i]][y3 y[i] y[i]]==false)q1.add(new zuobiao(x3,y3,zuo.time 1));} } if (a[x3 x[i]][y3 y[i]]=='T') { b[x3 x[i]][y3 y[i]]=true; q1.add(new zuobiao(x3 x[i],y3 y[i],zuo.time 1)); } } } } }
public static Comparator timecomepare2 =new Comparator()//实现comparator接口
{
	 public int compare(zuobiao a1,zuobiao a2)
 { return (int)(a1.time-a2.time);
 }
	};
}
 class zuobiao
{	
	int x;
	int y;
	int time;	//走的次数/时间
	public zuobiao(int x,int y,int time)
	{
		this.x=x;
		this.y=y;
		this.time=time; }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
 

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/79796267