POJ 2386 Lake Counting

鏈接：http://poj.org/problem?id=2386

Lake Counting

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 24263 Accepted: 12246

Description

Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John's field, determine how many ponds he has.

Input

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.

Output

* Line 1: The number of ponds in Farmer John's field.

Sample Input

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

Sample Output

3

Hint

OUTPUT DETAILS:

There are three ponds: one in the upper left, one in the lower left,and one along the right side.

Source

USACO 2004 November

大意——給你一個n*m的矩形網格。每一個格子里面要么是‘W’。要么是‘.’，它們分別表示水和旱地。

如今要你計算出有多少個池塘。

每一個池塘由若干個水組成，水能連接的方向有8個，僅僅要是能連接到的水都屬于一個池塘。

思路——一個簡單的DFS題。我們將所有的網格所有遍歷一次，假如我們找到一個池塘的源頭，就能夠進行一次計數。而且將眼下找到的池塘源頭標記為‘.’，那么下一次就不會反復訪問了。再從八個方向進行深搜，將能到達相鄰的‘W’所有標記，以免反復訪問。這樣最后得到的計數就是答案。

復雜度分析——時間復雜度:O(n*m),空間復雜度:O(n*m)

附上AC代碼：

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
//#pragma comment(linker, "/STACK:102400000, 102400000")
using namespace std;
typedef unsigned int li;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const double pi = acos(-1.0);
const double e = exp(1.0);
const double eps = 1e-8;
const int maxn = 105;
const int dir[8][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, -1}, {-1, 1}, {1, 1}}; // 8個方向
int n, m; // 矩形的行列
char mat[maxn][maxn]; // 矩形void dfs(int x, int y); // 深度優先搜索int main()
{ios::sync_with_stdio(false);while (~scanf("%d%d", &n, &m)){int cnt = 0;for (int i=0; i<n; i++)scanf("%s", mat[i]);for (int i=0; i<n; i++)for (int j=0; j<m; j++)if (mat[i][j] == 'W'){ // 找到池塘源頭，計數并深搜cnt++;dfs(i, j);}printf("%d\n", cnt);}return 0;
}void dfs(int x, int y)
{mat[x][y] = '.'; // 訪問過了。標記for (int i=0; i<8; ++i) // 從八個方向找相鄰的if (x+dir[i][0]>=0 && x+dir[i][0]<n && y+dir[i][1]>=0 &&y+dir[i][1]<m && mat[x+dir[i][0]][y+dir[i][1]]=='W')dfs(x+dir[i][0], y+dir[i][1]); // 找到相鄰的，繼續深搜
}