学步园

大概是这道题让我走入了DFS的大门吧。用了图形的遍历加上DFS的思想。

问题描述：

题目是给你一个N*M大小的水池，然后其中分为W和 . 两个字符，W代表了水，那么我们要算的就是八连通的水的个数。

算法思想：

在最外层做一个N*M的循环，把整个图用最naive的方法遍历一遍，检查是不是有W的地方。

在每一个W的地方开始运行dfs这个函数，这个函数的作用是

首先将该点设为 . ，也就是记下来我们已经到过这个地方，并且在之后用递归遍历其周围八个点

在这八个点中，如果出现W，那么以此点为起点再进行dfs。

然后在最外部dfs执行一次便把结果加一，那么最后便得到了我的结果。

代码部分：

#include <iostream>
using namespace std;

char field[117][117];
int n, m;

void dfs(int x, int y) {
	field[x][y] = '.';
	field[x][y] = 1;
	for (int i = -1; i <= 1; ++i) {
		for (int j = -1; j <= 1; ++j) {
			if (x + i > 0 && x + i <= n && y + j > 0 && y + j <= m && field[x + i][y + j] == 'W') {				
				dfs(x + i, y + j);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char s;
			cin >> s;
			field[i][j] = s;
		}
	}

	int res = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++) {
			if (field[i][j] == 'W') {
				dfs(i, j);
				res++;
			}
		}
	}

	cout << res << endl;
	return 0;
}

最后总结：

最后交的时候发现了很多用的内存和时间比我成倍缩小的，感觉还是too naive。多年以后回头看这篇文章，应该会有多一点感悟吧。