#BOJ 1012有機白菜

有機白菜
https://www.acmicpc.net/problem/1012

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	93408	35816	24260	36.560%

質問する
次世代農業従事者のハンナは、江原道高寒(カンウォンド・コ寒)地域で有機白菜を栽培することにした.白菜を農薬で栽培しなければ害虫から白菜を守ることが重要なので、ハンナは害虫防止に有効な白菜ミミズを購入することにした.このミミズは白菜の近くに生息し、害虫を捕食することで白菜を保護する.特に、ある白菜に白いミミズが住んでいれば、このミミズは隣の他の白菜に移動することができ、これらの白菜も害虫の保護を受けることができる.1本の白菜の上下左右4方向に異なる白菜がある場合は隣接しています.
ハンナが白菜を植える畑は平らではなく,白菜を植える場所はみなそろっている.白菜が集まっているところに白菜のミミズが1匹あればいいので、隣接する白菜がいくつか分布しているかを調べてみると、全部で何匹必要かがわかります.例えば、白菜畑が以下のように構成されている場合、白菜ミミズは少なくとも5匹必要である.0は白菜を植えていない土地を表し、1は白菜を植えた土地を表す.
1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 1 1
0 0 0 0 1 0 0 1 1 1
入力
入力された第1行は、試験例の個数Tを与える.次の行から、各試験例について、第1行は、キャベツ栽培地の横長M(1≦M≦50)および縦長N(1≦N≦50)およびキャベツ栽培場所の個数K(1≦K≦2500)を与えた.次いでK行はハクサイの位置X(0≦X≦M−1),Y(0≦Y≦N−1)を与える.2つの白菜が同じ位置にある場合はありません.
しゅつりょく
各試験箱について、所望の最小白菜白ミミズ数を出力する.
インプリメンテーション

#include <bits/stdc++.h>
using namespace std;

/*
BOJ  1012 유기농배추 BFS
배추의 개수 K [1<=K<=2500]
가로 M [1<=M<=50]
세로 N [1<=M<=50]
(x,y) : x 가로 , y : 세로
*/

int farm[52][52]; // 0으로 초기화
bool visited[52][52];

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


int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int testcase = 0;
	cin >> testcase; // 몇번 테스트할건지 입력

	while (testcase--)
	{
		int answer = 0;

		int col, row; //배추밭의 가로길이 , 세로길이 
		cin >> col >> row;

		//배추개수
		int number;
		cin >> number;

		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				visited[i][j] = false;
				farm[i][j] = 0;
			}
		}


		while (number--)
		{
			int x, y; // (가로,세로)
			cin >> x >> y;
			farm[y][x] = 1;
		} // 배추가 있는 곳을 1로 받음

		queue<pair<int, int>> Q;
		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				if (farm[i][j] == 0 || visited[i][j] == true) continue;
				answer++;
				Q.push({ i,j });
				visited[i][j] = true;

				while (!Q.empty())
				{
					auto cur = Q.front(); Q.pop();
					for (int dir = 0; dir < 4; dir++)
					{
						int nx = cur.first + dx[dir];
						int ny = cur.second + dy[dir];
						if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
						if (farm[nx][ny] == 0 || visited[nx][ny] == true) continue;
						Q.push({ nx,ny });
						visited[nx][ny] = true;
					}
				} //bfs
			}
		}
		cout << answer << '\n';

	}

	return 0;
}