問題描述
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]);}}} } }

總結

以上是生活随笔為你收集整理的杭电1241java实现dfs的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。