杭电1241java实现dfs

问题描述
GeoSurvComp地质调查公司负责检测地下油藏。 GeoSurvComp一次与一个大的矩形区域一起工作，并创建一个网格，将网格划分为多个方块。然后分别分析每个地块，使用传感设备确定该地块是否含有油。含油的情节被称为口袋。如果两个口袋相邻，则它们是同一个油藏的一部分。油藏可能相当大，可能含有大量的口袋。你的工作是确定网格中包含多少个不同的油藏。

输入
输入文件包含一个或多个网格。每个网格以含有m和n的行开始，网格中的行和列的数量由一个空格分隔。如果m = 0，则表示输入结束;否则1 <= m <= 100和1 <= n <= 100.之后是每行有n行的m行（不包括行尾字符）。每个字符对应一个图，既可以代表没有油的`*’，也可以代表一个油袋。

产量
对于每个电网，输出不同油量的数量。如果两个不同的口袋是水平，垂直或对角相邻的，则它们是同一个油藏的一部分。一个油藏不会超过100个口袋。

示例输入
1 1
*
3 5

• @ * @ *
  ** ** @
• @ * @ *
  1 8
  @@ **** @ *
  5 5
  **** @
• @@ * @
• @ ** @
  @@@ * @
  @@ ** @
  0 0

示例输出
0
1
2
2
思路：刚开始我以为是常规搜索题，当时想着遍历，标记，找相邻的，周围的，但是却发现可能后出现的会连结已经遍历过的，并且那个油田也不好表示，不能超过100不好判断。后来就看了别人学习了一下换了一种思路，找到油田的那个点开始遍历，遍历周围和他成为一个油田的所有满足条件的（包括100），把遍历过的点设为不可遍历。找到一个@就dfs一次，油田数量就增加一次。注意参数的重置问题。
代码如下：

import java.util.Scanner;
public class 杭电1241 {
	static int d[][]= {{-1,0},{-1,1},{-1,-1},{0,1},{0,-1},{1,0},{1,-1},{1,1}};//八个方向
	static int m,n,number,value;
	static char a[][];
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext())
		{ m=sc.nextInt();//行 n=sc.nextInt();//列 if(m==0&&n==0)break; sc.nextLine(); a=new char[m][n]; for(int i=0;i<m;i  ) { String a1=sc.nextLine(); a[i]=a1.toCharArray(); } for(int i=0;i<m;i  ) { for(int j=0;j<n;j  ) { if(a[i][j]=='@') {a[i][j]='*';number=0;dfs(i,j);value  ;} } } System.out.println(value); value=0;
		} }
	private static void dfs(int x1, int y1) { for(int i=0;i<8;i  ) { if(x1 d[i][1]>=0&&x1 d[i][1]<m&&y1 d[i][0]>=0&&y1 d[i][0]<n)//不超届； { if(a[x1 d[i][1]][y1 d[i][0]]=='@'&&number<100) { a[x1 d[i][1]][y1 d[i][0]]='*'; dfs(x1 d[i][1],y1 d[i][0]); } }
		} }
}


  

 

  
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
 

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

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