PKU 2386 Lake Counting

http://acm.pku.edu.cn/JudgeOnline/problem?id=2386

• 典型的な幅優先探索

int main()
{
	int N, M;
	cin >> N >> M;
	static bool wall[128][128];
	memset(wall, -1, sizeof(wall));
	for (int y = 1; y <= N; ++y) {
		for (int x = 1; x <= M; ++x) {
			char c;
			cin >> c;
			wall[x][y] = (c != 'W');
		}
	}

	static bool visited[128][128];
	memset(visited, 0, sizeof(visited));

	int answer = 0;
	for (int startX = 1; startX <= M; ++startX) {
		for (int startY = 1; startY <= N; ++startY) {
			if (visited[startX][startY] || wall[startX][startY]) {
				continue;
			}
			++answer;
			visited[startX][startY];

			deque<int> q;
			q.push_back(startX);
			q.push_back(startY);
			while (!q.empty()) {
				const int x = q.front();
				q.pop_front();
				const int y = q.front();
				q.pop_front();

				for (int dx = -1; dx <= 1; ++dx) {
					for (int dy = -1; dy <= 1; ++dy) {
						const int nextX = x + dx;
						const int nextY = y + dy;
						if (visited[nextX][nextY] || wall[nextX][nextY]) {
							continue;
						}
						visited[nextX][nextY] = true;

						q.push_back(nextX);
						q.push_back(nextY);
					}
				}
			}
		}
	}

	cout << answer << endl;
}