[백준] 1012번: 유기농 배추~

 

#include <iostream>
#include <queue>
using namespace std;

int field[52][52];
int row, col;

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

queue<int> q;

void caseSet()
{
	int K,tempRow,tempCol;
	cin >> col >> row >> K;
	
	for(int i=0; i<52; i++)
	{
		for(int j=0; j<52; j++)
		{
			field[i][j] = 0;
		}
	}
	
	for(int i=0; i<=row+1; i++)
	{
		field[i][0] = 2;
		field[i][col+1] = 2;
	}
	
	for(int i=0; i<=col+1; i++)
	{
		field[0][i] = 2;
		field[row+1][i] = 2;
	}
	
	for(int i=0; i<K; i++)
	{
		cin >> tempCol >> tempRow;
		field[tempRow+1][tempCol+1] = 1;
	}
}

void erase(int i, int j)
{
	int r,c;
	field[i][j] = 0;
	q.push(i); q.push(j);
	
	while(!q.empty())
	{
		r = q.front(); q.pop();
		c = q.front(); q.pop();
		
		for(int k=0; k<4; k++)
		{
			if(field[r+dy[k]][c+dx[k]] == 1)
			{
				field[r+dy[k]][c+dx[k]] = 0;
				q.push(r+dy[k]);
				q.push(c+dx[k]);		
			}
		}
	}
}	

int getNumOfWorm()
{
	int count = 0;
	for(int i=1; i<=row; i++)
	{
		for(int j=1; j<=col; j++)
		{
			if(field[i][j] == 1)
			{
				erase(i,j);
				count++;
			}
		}
	}
	return count;
}

int main() {
	int T;
	cin >> T;
	for(int it=0; it<T; it++)
	{
		caseSet();
		cout << getNumOfWorm() << endl;
	}
	return 0;
}