APS/백준
[14716] 현수막 C++
문래동까마귀
2022. 3. 5. 00:50
https://www.acmicpc.net/problem/14716
14716번: 현수막
혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라.
www.acmicpc.net
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int M, N;
int cnt = 0;
int map[251][251] = { 0 };
int visit[251][251] = { 0 };
void dfs(int y, int x) {
int direct[8][2] = {
-1,-1,
-1,0,
-1,1,
0,-1,
0,1,
1,-1,
1,0,
1,1
};
for (int i = 0; i < 8; i++) {
int dy = y + direct[i][0];
int dx = x + direct[i][1];
if (dy < 0 || dx < 0 || dy >= M || dx >= N)
continue;
if (visit[dy][dx] == 1)
continue;
if (map[dy][dx] == 1) {
visit[dy][dx] = 1;
dfs(dy, dx);
}
}
}
int main() {
ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
cin >> M >> N;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 1 && visit[i][j] != 1) {
dfs(i, j);
visit[i][j] = 1;
cnt++;
}
}
}
cout << cnt;
return 0;
}