白駿4963号島の個数



質問リンク

コードの説明


対角線方向も探索する必要があるので,方向配列を8個に増やした.
また,visit配列を用いてmainから入る場合,BFS関数内でも探索した場所でないことが重要である.
入力を受け取った場合でもwhileゲート内でmap,島の個数cntなどの初期化を継続する.

ソースコード

#include<iostream>
#include<queue>
#include <vector>
#define Max 51
using namespace std;
int cnt;
int map[Max][Max];
int w, h;
int dy[] = { -1,-1,-1,1,1,1,0,0 };
int dx[] = { -1,1,0,1,-1,0,1,-1 };
bool visited[Max][Max];
void bfs(int y,int x) {

	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 8; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;

			if (map[ny][nx] == 1 && !visited[ny][nx]) {
				q.push({ ny,nx });
				visited[ny][nx] = true;
			}
		}
	}



}
void init() { //map 초기화, cnt 초기화
	cin.tie(NULL);
	cout.tie(NULL);
	cnt = 0;
	for (int y = 0; y < h; y++) {
		for (int x = 0; x < w; x++) {
			map[y][x] = { 0 };
			visited[y][x] = false;

		}
	}
}
int main() {
	vector<int> cntt;
	while (1) {
		
		cin >> w >> h; //w 너비 h 높이
		init();
		if (w == 0 && h == 0) break;

		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				cin >> map[y][x];

			}
		}

		for(int y=0;y<h;y++){
			for (int x = 0; x < w; x++) {

				if (map[y][x] == 1 && !visited[y][x]) {
					cnt++;
					bfs(y, x);
					
				}
			}
		}
		
		cntt.push_back(cnt);
	}

	for (int i = 0; i < cntt.size(); i++) {
		cout << cntt[i] << endl;
	}

	return 0;
}