算法學習--水窪的數量

深度優先搜尋之水窪的數量

原創 蠕動的二哈 最後釋出于2018-10-26 17:33:14 閱讀數 379 收藏

展開

1. 問題描述：

水窪數目有一個大小為N * M的院子，雨後積起了水，

八連通的積水被認為是連在一起的，請求出園子裡面總共有多少水窪（八連通指的是下圖中相對w大的*部分）

***
*w*
***
           

限制條件

N, M <=100

樣例：

輸入

N = 10, M = 12

園子如下圖(‘W’表示積水，’.'表示沒有積水)

W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
           

輸出

//水窪數（DFS）
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

int N, M;//N行M列的地圖

void dfs(char** arr, int i, int j) {
	arr[i][j] = '.';//周遊過的地方變成幹燥

	//八個方向
	//if (i > 0 && arr[i - 1][j] == 'W')dfs(arr, i - 1, j);//上方
	//if (i < N - 1 && arr[i + 1][j] == 'W')dfs(arr, i + 1, j);//下方
	//if (j > 0 && arr[i][j - 1] == 'W')dfs(arr, i, j - 1);//左方
	//if (j < M - 1 && arr[i][j + 1] == 'W')dfs(arr, i, j + 1);//右方
	//if (i > 0 && j > 0 && arr[i - 1][j - 1] == 'W')dfs(arr, i - 1, j - 1);//左上方
	//if (i > 0 && j < M - 1 && arr[i - 1][j + 1] == 'W')dfs(arr, i - 1, j + 1);//右上方
	//if (i < N - 1 && j > 0 && arr[i + 1][j - 1] == 'W')dfs(arr, i + 1, j - 1);//左下方
	//if (i < N - 1 && j < M - 1 && arr[i + 1][j + 1] == 'W')dfs(arr, i + 1, j + 1);//右下方

	for (int n = -1; n <= 1; n++) {
		for (int m = -1; m <= 1; m++) {
			if (n == 0 && m == 0)continue;

			if (i + n >= 0 && i + n <= N - 1 && j + m >= 0 && j + m <= M - 1) {
				if (arr[i + n][j + m] == 'W')
					dfs(arr, i + n, j + m);
			}
		}
	}
}

int main() {
	cin >> N >> M;
	int count = 0;
	char** ch_arr = new char*[N];
	for (int i = 0; i < N; i++){
		ch_arr[i] = new char[M];
		cin >> ch_arr[i];
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++){
			if (ch_arr[i][j] == 'W') {
				dfs(ch_arr, i, j);
				count++;
			}
		}
	}
	cout << count << endl;
	return 0;
}