算法学习--水洼的数量

深度优先搜索之水洼的数量

原创 蠕动的二哈 最后发布于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;
}