Q1

Q1 DFS

Description

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits.GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil.A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

有一家地質調査公司叫做GcoSurComp,負責探測地下的石油儲量。該公司 的工作方式是將要調查的大塊矩形土地，分成許多1平方公尺的小塊上地， 接著每小塊逐個分析是否含有石油。 含石油的小塊土地稱為油區(pockct)·如果是相鄰的兩個油區，可視為同一 塊油田的一部分。除了上下左右鄰居視為相鄰以外，對角線相差一格也視為 相鄰。如下圖所示。「@」表示油區， 「*」 表示不含石油之土地。在此例 中，所有油區都相鄰,視為同一塊油田。每塊油田的範圍可能相當大，也就 由相當多的油區組成。本題要求給定一塊已經分m x n 的矩形土地,，請計算 其中的油田數量。

Input

The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 ≤ m ≤ 100 and 1 ≤ n ≤ 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either ‘*’, representing the absence of oil, or ‘@’, representing an oil pocket.

Q1: DFS 輸入與輸出說明 • 輸入的第一列表示一組測試資料的m 和 n, 表示該組測資為 m X n 的土地, m 與 n 都介於1到100之間; 接著會給定該土地每格內的含油情況, “@” 表示油 區, “ * ”表示非油區。若一組測資的第一列m與n都為0, 則表示結束。最後， 輸出每組測資的油田數量。

Output

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

Sample Input 1

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

Sample Output

0
1
2
2
2

#include<stdio.h>
int p[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
char ch[100][100];
int m,n;
void dfs(int x,int y)//It is rare to be the dfs function
{
      int i,xx,yy;
      for(i=0;i<8;i++)
     {
         xx=x+p[i][0];
         yy=y+p[i][1];
         if(xx<0||xx>=m||yy<0||yy>=n)
              continue;
         if(ch[xx][yy]=='*')
              continue;
         ch[xx][yy]='*';
         dfs(xx,yy);               
     }    
}
int main()
{
  int i,j,count;
  while(scanf("%d%d",&m,&n)&&m+n)
  {
   for(i=0;i<m;i++)
   scanf("%s",ch[i]);
   count=0;
   for(i=0;i<m;i++)
    for(j=0;j<n;j++)
    {
     if(ch[i][j]=='@')
     {
      dfs(i,j);
      count++;
     }               
    }                    
    printf("%d\\n",count);
  }   
 return 0;
}

HINT • Start with the small patch of land at grid [0][0] and search for oil regions one by one. If an oil region is found, begin from that oil region and use depth-first search (DFS) to find all the adjacent oil regions, and after finding them, add 1 to the count of oil fields. During the execution, both the searched oil regions and non-oil regions must be recorded. Therefore, skip the areas that have already been checked to avoid recounting the same oil field. When writing the DFS program, using recursion is easier to write and shortens the code. • The following uses a graph to explain the operation of the DFS algorithm, which will traverse each node in the entire graph one by one. The process is prioritized by 'depth', and when all nodes have been traversed, it will return to the starting point. As shown in the graph below, assume starting from point 1, and always take the leftmost path at a fork. The execution process of DFS is as follows: • 1. The sequence is: 1->2->4->6, at point 6 there are no unvisited points, so return to point 4. • 2. At point 4 there are no unvisited points, return to point 2 • 3. From point 2 it is possible to go to point 5, and since point 5 has not been visited, proceed to point 5. • At point 5, no unvisited points can be found, return to point 2. • 4. Return to point 1, find that point 3 has not been visited, so proceed to point 3. • 5. Return to the starting point 1. There are no unvisited points, the algorithm ends. • Thus, the order of traversal for DFS is: 1→2->4->6→5→3

HINT: • 先從第[0][0]格小塊土地開始，逐一找尋油區。若找到油區，則從該油區開 始,使用深度優先搜尋(depth-first search, DFS)將和該油區相鄰的所有油區全 部找出,找出後將油田數量加1。在執行過程中，搜索過的油區、非油區皆需 記錄。因此，遇到已經檢查過的區域就跳過，以免重複計算同一塊油田，撰 寫 DFS 程式時，使用遞迴方式較容易撰寫程式而且縮短程式碼。 • 以下用圖形(graph)解釋DFS演法的運作方式,它會將整個圖中可以走的節點 (node)逐一走過。執行過程是以「深度」(depth)為優先,當所有節點都走過, 將會走回起點·以下圖為例,假設從點1開始,且遇到岔路皆以最左邊的點先走。 以下為DFS的執行過程: • 1.順序為:1->2->4->6, 在點6不到未走過的點,故退回點4. • 2.在點4不到未走過的點,退回點2 • 3由點2可以走到點5,且點5末走過,故走到點5。 在點5找不到未走過的點,退回點2。 • 4.退回點1,發現點3未走過,,故走到點3。 • 5.退起點1。沒有末走過的點,演算法結束。 • 所以DFS走訪的順序為:1→2->4->6→5→3

source code: https://blog.csdn.net/m0_58245389/article/details/118651671