---
# System prepended metadata

title: UVA 572 - Oil Deposits
tags: [DFS]

---

# UVA 572 - Oil Deposits
### 題意:
GeoSurvComp 每次會調查一大片矩形土地，將其劃分成許多方格區塊（grid）。
接著使用感應設備來逐一分析每一塊土地，判定該格是否含有石油。

一塊含有石油的格子稱為「油井」（pocket）。
如果兩塊油井是相鄰的，則它們屬於同一個油田（oil deposit）。

你的工作是：判斷一個 grid 中總共有多少個不同的油田。

### Sample Input:

輸入包含一個或多個地圖。
每組測資的第一行有兩個整數 m、n，代表地圖的行數和列數。(1 ≤ m ≤ 100, 1 ≤ n ≤ 100)
m = 0 時，輸入結束。

接下來會有 m 行，每行包含 n 個字元，每個字元代表一塊地：
* '*' 表示這塊地不含油。
* '@' 表示這塊地是一塊油井。

```=
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
```
### Sample Output:
對每張地圖，輸出該地圖中有多少個不同的油田。
==若兩塊油井橫向、縱向或斜向相鄰，就屬於同一個油田。==
```=
0
1
2
2
```

### 程式碼:
遇到油井就去跑 DFS(跑完記得標記跑完，我是直接殺掉)，跑幾次就代表有幾個油田。
```cpp=
#include <bits/stdc++.h>
#define vvi vector<vector<int>>
using namespace std;

vvi dir = {{1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}};

void DFS(vvi& g, int i, int j, int m, int n){    // 本來忘記&，會直接無限迴圈 XD
	g[i][j] = 0;
	for (int k = 0; k < 8; k++) {
		int tmpi = i + dir[k][0]; int tmpj = j + dir[k][1];
		if (tmpi >= m || tmpj >= n || tmpi < 0 || tmpj < 0) continue;
		if (g[tmpi][tmpj] == 1) DFS(g, tmpi, tmpj, m, n);
	}
	return;
}

int main(){
	int m, n; char c;
	while(cin >> m >> n && m != 0) {
		vvi g(m, vector<int>(n, 0));
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				cin >> c;
				if (c == '@') g[i][j] = 1;
			}
		}
		int cnt = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (g[i][j] == 1){
					DFS(g, i, j, m, n);
					cnt++;
				}
			}
		}
		cout << cnt << endl;
	}
	return 0;
}
```