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;
}