白駿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;
}
Reference
この問題について(白駿4963号島の個数), 我々は、より多くの情報をここで見つけました
https://velog.io/@trevor522/백준-4963번-섬의개수
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#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;
}
Reference
この問題について(白駿4963号島の個数), 我々は、より多くの情報をここで見つけました https://velog.io/@trevor522/백준-4963번-섬의개수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol