PKU 1562 Oil Deposits

• 幅優先探索
• 広げる方向は8方向

static const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
static const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
	for (int height, width; cin >> height >> width && (height || width); ) {
		static char maze[128][128];
		memset(maze, '*', sizeof(maze));

		for (int y = 1; y <= height; ++y) {
			for (int x = 1; x <= width; ++x) {
				cin >> maze[x][y];
			}
		}

		int answer = 0;
		for (int startY = 1; startY <= height; ++startY) {
			for (int startX = 1; startX <= width; ++startX) {
				if (maze[startX][startY] != '@') {
					continue;
				}

				++answer;
				deque<int> q;
				q.push_back(startX);
				q.push_back(startY);
				maze[startX][startY] = '*';
				while (!q.empty()) {
					const int x = q.front();
					q.pop_front();
					const int y = q.front();
					q.pop_front();

					for (int dir = 0; dir < 8; ++dir) {
						const int nextX = x + dx[dir];
						const int nextY = y + dy[dir];

						if (maze[nextX][nextY] != '@') {
							continue;
						}

						maze[nextX][nextY] = '*';
						q.push_back(nextX);
						q.push_back(nextY);
					}
				}
			}
		}

		cout << answer << endl;
	}
}