[실2] 1012 - 유기농 배추

x y로 푸는 사람들한텐 안맞을듯

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define FAST_IO() ios::sync_with_stdio(0); cin.tie(0);

pair<int, int> dir[]
{
	{1, 0},	  // 상
	{-1, 0},  // 하
	{0, -1},  // 좌
	{ 0, 1 },  // 우
};

vector<vector<int>> map;
int t, h, w, k;

void Dfs(int y, int x)
{
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dir[i].first, nx = x + dir[i].second;

		if (ny >= h ||
			ny < 0 ||
			nx >= w ||
			nx < 0)
			continue;

		if (map[ny][nx])
		{
			map[ny][nx] = false;
			Dfs(ny, nx);	
		}
	}
}

int main()
{
	FAST_IO();

	cin >> t;

	while (t--)
	{
		int cnt = 0;
		cin >> h >> w >> k;
		map = vector<vector<int>>(h, vector<int>(w));

		while (k--)
		{
			int a, b;
			cin >> b >> a;
			map[b][a] = 1;
		}
		for (int y = 0; y < h; y++)
		{
			for (int x = 0; x < w; x++)
			{
				// 주변 배추 정리
				if (map[y][x])
				{
					map[y][x] = false;
					Dfs(y, x);
					cnt++;
				}
			}
		}
		cout << cnt << endl;
	}
	return 0;
}