杭电oj1072java实现bfs

Nightmare
问题描述
伊格内修斯昨晚有一场噩梦。他发现自己身陷迷宫，身上有一枚定时炸弹。迷宫有一个出口，在炸弹爆炸之前，伊格内修斯应该走出迷宫。炸弹的最初爆炸时间设定为6分钟。为了防止炸弹爆炸，伊格内修斯必须缓慢移动，即从一个区域移动到最近的区域（也就是说，如果Ignatius现在站在（x，y）上，他只能在（x 1， y），（x-1，y），（x，y 1）或（x，y-1））在1分钟内。迷宫中的某个区域包含一个炸弹重置设备。他们可以将爆炸时间重置为6分钟。

鉴于迷宫布局和伊格内修斯的起始位置，请告诉伊格纳修斯他是否可以走出迷宫，如果可以的话，输出他必须用来寻找迷宫出口的最短时间，否则输出-1。

以下是一些规则：
我们可以假设迷宫是2阵列。
2.每分钟，伊格内修斯都只能到最近的一个地方，他不应该走出边界，当然他也不能在墙上行走。
3.如果伊格内修斯在爆炸时间变为0时到达出口处，他就无法离开迷宫。
4.如果伊格内修斯在爆炸时间变为0时到达包含炸弹休息装备的区域，他不能使用该装备重置炸弹。
5.炸弹重置设备可以根据需要多次使用，如果需要的话，伊格内修斯可以根据需要多次进入迷宫中的任何区域。
6.重置爆炸时间的时间可以忽略，换句话说，如果伊格内修斯到达包含炸弹休息装备的区域，并且爆炸时间大于0，则爆炸时间将重置为6。

输入
输入包含多个测试用例。输入的第一行是单个整数T，它是测试用例的数量。 T测试用例如下。
每个测试用例都以两个表示迷宫大小的整数N和M（1 <= N，Mm = 8）开始。然后N行，每行包含M个整数。该数组表示迷宫的布局。
有五个整数表示迷宫中不同类型的区域：
0：该地区是一堵墙，伊格内修斯不应该走上它。
1：该地区没有任何东西，伊格内修斯可以在其上行走。
2：伊格内修斯的起跑位置，伊格内修斯开始逃离这个位置。
3：迷宫的出口，依纳爵的目标位置。
4：该区域包含一个炸弹重置设备，Ignatius可以通过步行到这些区域来延迟爆炸时间。

产量
对于每个测试案例，如果Ignatius可以走出迷宫，那么你应该输出他需要的最短时间，否则你应该输出-1。

示例输入
3
3 3
2 1 1
1 1 0
1 1 3
4 8
2 1 1 0 1 1 1 0
1 0 4 1 1 0 4 1
1 0 0 0 0 0 0 1
1 1 1 4 1 1 1 3
5 8
1 2 1 1 1 1 1 4
1 0 0 0 1 0 0 1
1 4 1 0 1 1 0 1
1 0 0 0 0 3 0 1
1 1 4 1 1 1 1 1

示例输出
4
-1
13
要求找到最小的走路次数值，并且用深搜无法剪枝，显然是一道宽搜题。有一些注意点：
1：普通的位置可以走多次，不需要标记，因为有可能就为了去吃重置炸弹的装置就再某个边角地方进去一下出来一下。
2：重置的点需要标记，因为重置的点走过一次就够了，因为第一次重置该点的总步数一定是最小的。
3：要用优先队列优化，先出步数最少的那个点，找到满足条件的值就立马break；因为优先队列先弹出的是步数最小的那个点，后面再弹出即使满足条件步数一定大于该点。
附上代码：

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
/*
 * 宽搜，优先队列优化
 */
public class 杭电1072bfs {
	static int n,m,x1=0,y1=0,x2,y2,min;//行 列 初始点 结束点 结果
	static int d[][]= {{1,0},{0,-1},{-1,0},{0,1}};//上左下右	
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in); int T=sc.nextInt();//测试用例			
		while(T-->0)
		{ min=64;	//看清范围，这个是极限		  n=sc.nextInt();m=sc.nextInt();//行 列 int a[][]=new int[n][m];	//储存数据  for(int i=0;i q1=new PriorityQueue<>(valuecompare);//优先队列		
		q1.add(new node(x1,y1,0,6));
		while(!q1.isEmpty())
		{ node exa=q1.poll();//返回头节点并删除			 int x=exa.x,y=exa.y; if(exa.x==x2&&exa.y==y2) {if(exa.time>0&&min>exa.value) {min=exa.value;}} else if(exa.time==0) {;} else for(int i=0;i<4;i ) { if(x d[i][1]<0||y d[i][0]<0||x d[i][1]>=n||y d[i][0]>=m){continue;}//不越界 else { if(a[x d[i][1]][y d[i][0]]==1) //普通路径 { q1.add(new node(x d[i][1],y d[i][0],exa.value 1,exa.time-1)); } else if(a[x d[i][1]][y d[i][0]]==4)//重置区 { if(exa.time==1) {} else { q1.add(new node(x d[i][1],y d[i][0],exa.value 1,6)); a[x d[i][1]][y d[i][0]]=0; } } else if((a[x d[i][1]][y d[i][0]]==3))//结果区，让再循环外判断 { q1.add(new node(x d[i][1],y d[i][0],exa.value 1,exa.time-1));; } } }
		} }
	public static Comparator valuecompare =new Comparator()//接口 { @Override public int compare(node arg0, node arg1) { return (int)(arg0.value-arg1.value); } };
}
class node//点
{
	int x;
	int y;
	int value;
	int time;
	public node(int x,int y,int value,int time)
	{
		this.x=x;
		this.y=y;
		this.value=value;
		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
 

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

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