杭电1044java实现dfs bfs

Collect More Jewels
问题描述
它写在“夫人的书：创世之后，残酷的神摩洛克反抗了造物主马尔杜克的权威。摩尔从马尔杜克那里偷走了众神中所有神器中最强大的一件，也就是叶多尔的护身符，并且他隐藏了它在Gehennom的阴暗洞穴，现在潜伏在他身边的Under World，并且是他的时间。

你的女神女士寻求拥有护身符，并与它一起获得应得的尊荣，胜过其他诸神。

你是一位新接受过训练的漫步者，从出生时就已经成为了女士的乐器。你注定要为你的神祗恢复护身符，或者在企图中死去。你的命运已经到了。为了我们所有人：勇敢地与The Lady一起去！

如果你曾经玩过电脑游戏NETHACK，你必须熟悉上面的引用。如果你从来没有听说过，不要担心。你会很快学会它（并且很喜欢它）。

在这个问题上，你是冒险家，处于危险的地下城。你被告知地牢将崩溃。您必须在给定时间内找到出口楼梯。但是，你不想空手离开地牢。地牢里有很多珍贵的珠宝。在你离开之前尝试收集他们中的一些。一些珠宝更便宜，有些更昂贵。所以你会尽力使你的收藏最大化，更重要的是，要及时离开地下城。

输入
标准输入将包含多个测试用例。输入的第一行是一个整数T（1 <= T <= 10），它是测试用例的数量。接下来是T测试用例，每个测试用例都有一个空白行。

每个测试用例的第一行包含四个整数W（1≤W≤50），H（1≤H≤50），L（1≤L≤1000000）和M（1≤M≤50） = 10）。地牢是一个矩形区域，宽度为W，高度为H。 L是您需要到达出口的时间限制。只要目标区块位于地下城内并且不是墙壁，您就可以移动到每个时间单位上下左右的相邻区块之一。游戏开始时，时间从1开始。 M是地下城里珠宝的数量。一旦冒险家在这个街区，珠宝就会被收集起来。这不会花费额外的时间。

下一行包含M个整数，这是珠宝的值。

接下来的H行将包含W个字符。他们用下列符号表示地牢地图：

[*]标志着一堵墙，你无法移动;
[。]标记一个空的空间，你可以在其中移动;
[@]标志着冒险家的初始位置;
[<]标记出口楼梯;
[A] - [J]标志着珠宝。

输出
结果应该针对标准输出。在一行中以“案例＃：”开始每个案例，其中＃是从1开始的案例编号。连续两个案例应该由一个空行分隔。在最后的测试用例之后不应该产生空白行。

如果冒险者可以在规定的时间内到达出口楼梯，可以打印“最好成绩为S”的句子，其中S是他可以沿途收集的珠宝的最大值;否则在单行上打印“不可能”一词。
Sample Input

3

4 4 2 2
100 200
****
*@A*
*B<*
****

4 4 1 2
100 200
****
*@A*
*B<*
****

12 5 13 2
100 200
************
*B.........*
*.********.*
*@...A....<*
************
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Sample Output
Case 1:
The best score is 200.

Case 2:
Impossible

Case 3:
The best score is 300.
思路：先用bfs预估记。记录点点之间的最短距离。然后再dfs遍历点点。不可以直接遍历图。图太大会直接爆时。我处理的方式是建立dp【】【】【】三维代表xy到第m个点的距离。也可以用dp【】【】【】【】表示点的距离。因为我的m点有专门记录。dfs开始也可以从起始点开始，遍历到结束点后就停止。
代码如下：

import java.util.ArrayDeque;
	import java.util.Queue;
	import java.util.Scanner;
	
      public class 杭电1044 {
		static int dx[]= {0,1,0,-1};
		static int dy[]= {1,0,-1,0};
		static int x1=0,y1=0,x2=0,y2=0,t=0,w=0,h=0,m=0;//起点  结束点    时间  宽   高  珠宝数量
		static int score=0;//记录获取的分数
		static int m1[];//记录珠宝价值
		static int path=0;//两点之间的最短路径
		static char mi[][]=new char[50][50];//地图
		public static void main(String[] args)  {
			 Scanner sc=new Scanner(System.in);
			 int T=sc.nextInt();//测试用例			
			 for(int T1=1;T1<T 1;T1  )
			 { 
				 sc.nextLine();//空格是输入的空格，不是输出的空格
				  w=sc.nextInt();//宽（左右
				  h=sc.nextInt();//高				
				 t=sc.nextInt();//时间
				  m=sc.nextInt();//珠宝数量				  
				  m1=new int [m 1];//储存珠宝价值
				  int m2[][]=new int[m 1][2];//存宝物坐标 最后一位存结束点的坐标
				 for(int i=0;i<m;i  )
				 {m1[i]=sc.nextInt();}//珠宝的价值
				 sc.nextLine();
				 for(int i=0;i<h;i  )//输入地图
				 {
					 String a=sc.nextLine();
					 mi[i]=a.toCharArray();
				 }
				 for(int i=0;i<h;i  )
				 {
					 for(int j=0;j<w;j  )
					 {						
						 if(mi[i][j]=='@') {x1=i;y1=j;mi[i][j]='.';}//记录完这个位置就将他变成普通路径，方便后面计算就只有墙不能走
						 if(mi[i][j]=='<') {x2=i;y2=j;mi[i][j]='.';}
						 //ABCD始有顺序的可以转化为对应int值
						 if('A'<=mi[i][j]&&mi[i][j]<='A' m) {m2[mi[i][j]-'A'][0]=i;m2[mi[i][j]-'A'][1]=j;}//粗存珠宝所在位置。
					 }				
				 }
				m2[m][0]=x2;m2[m][1]=y2;
				//记录 xy  到第m个珠宝的价值（前提可以到达）因为前面有数组粗存珠宝坐标	
				int dp[][][]=new int [h][w][m 1];			
				 if(bfs(x1,y1,x2,y2))//可以到达
				 {					
					 score=0;
					 boolean jud[]=new boolean[m 1];					
					 dfs(x1,y1,0,0,jud,m2,dp);				 
					 System.out.println("Case " T1 ":");
					 if(T1==T) {System.out.println("The best score is " score ".");}
					 else  {System.out.println("The best score is " score ".");System.out.println();}				 
				 }
				 else//不可以到达
				 {					 
					  System.out.println("Case " T1 ":");
					  if(T1==T) {System.out.println("Impossible");}
					  else  { System.out.println("Impossible");System.out.println();}
				 }
			 }		
		}
		private static void dfs( int x, int y, int t2,int q, boolean[] jud, int[][] m2, int[][][] dp) {
			//System.out.println(q);
			if(x==x2&&y==y2) {if(t2<=t) {if(q>score) {score=q;}}}
			else if(t2 Math.abs(x-x2) Math.abs(y-y2)>t) {}
			else
				for(int i=0;i<m 1;i  )
				{								
					  if(!jud[i]&&dp[x][y][i]!=-1)
					{	
						  if(dp[x][y][i]==0)//没有初始过
					     { 
							  if(bfs(x,y,m2[i][0],m2[i][1])) {
								  jud[i]=true;dp[x][y][i]=path;//
								
									dfs(m2[i][0],m2[i][1],t2 path,q m1[i],jud,m2,dp);					
									jud[i]=false;}
							  else {
								  dp[x][y][i]=-1;//已经标记不能走
							  }						  
					     }
						  else //前面已经记录过，不需要重复bfs
						  {
							  jud[i]=true;
							dfs(m2[i][0],m2[i][1],t2 dp[x][y][i],q m1[i],jud,m2,dp);					
								jud[i]=false;
						  }
					}
				}
		}
		private static boolean bfs( int a1, int b1, int a2, int b2) {
			path=0;
			Queue<zuobiao> q1=new ArrayDeque();
			q1.add(new zuobiao(a1,b1,0));
			if(Math.abs(a1-a2) Math.abs(b2-b1)>t) {return false;}
			if(Math.abs(a1-x2) Math.abs(y2-b1)>t) {return false;}
			boolean b[][]=new boolean[h][w];
			b[a1][b1]=true;
			while(!q1.isEmpty())
			{
				zuobiao zuo=q1.poll();
				int x=zuo.x;int y=zuo.y;
				if(x==a2&&y==b2) {if(zuo.time<=t) {path=zuo.time;return true;}}
				else			
				for(int i=0;i<4;i  )
				{
					if(x dx[i]>=0&&x dx[i]<h&&y dy[i]>=0&&y dy[i]<w)//不出届
					{
						if(mi[x dx[i]][y dy[i]]!='*'&&!b[x dx[i]][y dy[i]])//可以移动  时间
						{
							if(zuo.time 1 Math.abs(y dy[i]-y2) Math.abs(x dx[i]-x2)<=t)
							{q1.add(new zuobiao(x dx[i],y dy[i],zuo.time 1));
							b[x dx[i]][y dy[i]]=true;}
						}
					}
				}				
			}
			return false;		
		}
		static class zuobiao
		 {
			 int x;
			 int y;
			 int time;
			 int value;
			 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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134