[백준/BOJ] 백준 17092번 : 색칠 공부

www.acmicpc.net/problem/17092

17092번: 색칠 공부

검정색 칸의 위치를 기준으로 해당 위치와, 주변 8방향 총 9곳을 확인하여 그곳이 중심인 3X3보드를 확인한다 그리고 중복해서 3X3보드를 확인하지 않기 위해 set <pair<int, int>> check;에 3X3보드의 가운데 위치를 저장하여 중복을 체크했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
using namespace std;

int h, w, n;
int dxdy[9][2] = { {0,0}, {0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1} };
set <pair<int, int>> board;
set <pair<int, int>>::iterator it;
set <pair<int, int>> check; //해당 위치가 가운데인 3X3 보드
vector<long long> cnt_info(10, 0);
long long maked_cnt = 0;

void Check(pair<int, int> here, int point_index)
{
	pair<int, int> point_here = make_pair(here.first + dxdy[point_index][0], here.second + dxdy[point_index][1]);

	int cnt = 0;

	//here위치가 3X3보드의 가운데인것을 확인한적이 있을때
	if (check.count(point_here) != 0)
		return;

	for (int i = 0; i < 9; i++)
	{
		pair<int, int> point_there = make_pair(point_here.first + dxdy[i][0], point_here.second + dxdy[i][1]);

		//이런 3X3보드는 없다
		if (point_there.first < 1 || point_there.first > h || point_there.second < 1 || point_there.second > w)
			return;

		//해당 위치가 검정칸일때
		if (board.count(point_there) != 0)
			cnt++;
	}


	check.insert(point_here);
	cnt_info[cnt]++;
	maked_cnt++;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> h >> w >> n;

	for (int i = 0; i < n; i++)
	{
		int r, c;

		cin >> r >> c;

		board.insert(make_pair(r, c));
	}

	for (it = board.begin(); it != board.end(); it++)
	{
		pair<int, int> here = (*it);
		for (int i = 0; i < 9; i++)
		{
			Check(here, i); //here위치를 기준으로 here위치와, 주변 8방향 총 9곳을 확인하여 그곳이 중심인 3X3보드를 확인한다
		}
	}

	cnt_info[0] = ((long long)(w - 2) * (long long)(h - 2)) - maked_cnt;

	for (int i = 0; i < 10; i++)
		cout << cnt_info[i] << "\n";
}