https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
bfs 가볍게 몸 풀기
#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<map>
#include<stack>
using namespace std;
struct Point {
int i, j, t, cnt;
char c;
};
void Prints(vector<vector<int>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<bool>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<char>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<vector<char>>>maps, int n, int m, int k) {
for (int t = 0; t < k; t++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[t][i][j];
}
cout << endl;
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<vector<bool>>>maps, int n, int m, int k) {
for (int t = 0; t < k; t++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[t][i][j];
}
cout << endl;
}
cout << endl;
}
cout << endl;
}
struct Data {
int score;
int index;
};
struct Word {
std::string word;
int count;
};
vector<bool>bVisited;
int main() {
vector<int>gCount;
while (true)
{
int w,h;
cin >> w >> h;
if (w == 0 && h == 0) break;
vector < vector<int >> maps;
vector<bool >tmpVisited(w, true);
vector < vector<bool >> bVisited(h,tmpVisited);
for (int i = 0; i < h; i++) {
vector<int>tmpMaps;
for (int j = 0; j < w; j++) {
int tmp;
cin >> tmp;
tmpMaps.push_back(tmp);
if (tmp == 1) {
bVisited[i][j] = false;
}
}
maps.push_back(tmpMaps);
}
int dirw[] = { 0,0,1,-1, 1, 1, -1, -1};
int dirh[] = { 1,-1,0,0, 1, -1, -1, 1};
int count = 0;
for (int z = 0; z < h; z++) {
for (int k = 0; k < w; k++) {
if (bVisited[z][k] == false) {
Point p;
p.i = z;
p.j = k;
count ++;
bVisited[z][k] = true;
queue<Point>q;
q.push(p);
while (!q.empty()) {
Point start = q.front();
q.pop();
for (int i = 0; i < 8; i++) {
int tmpDirw = start.j + dirh[i];
int tmpDirh = start.i + dirw[i];
if (tmpDirw == -1 || tmpDirh == -1 || tmpDirw >= w || tmpDirh >= h|| bVisited[tmpDirh][tmpDirw]==true) {
continue;
}
bVisited[tmpDirh][tmpDirw] = true;
Point tmpP;
tmpP.i = tmpDirh;
tmpP.j = tmpDirw;
q.push(tmpP);
}
}
}
}
}
gCount.push_back(count);
}
for (int i = 0; i < gCount.size(); i++) {
cout << gCount[i] << endl;
}
return 0;
}