[BOJ]白俊1012号有機白菜

リンク

https://www.acmicpc.net/problem/1012

質問する

次世代農業従事者のハンナは、江原道高寒(カンウォンド・コ寒)地域で有機白菜を栽培することにした.白菜を農薬で栽培しなければ害虫から白菜を守ることが重要なので、ハンナは害虫防止に有効な白菜ミミズを購入することにした.このミミズは白菜の近くに生息し、害虫を捕食することで白菜を保護する.特に、ある白菜に白いミミズが住んでいれば、このミミズは隣の他の白菜に移動することができ、これらの白菜も害虫の保護を受けることができる.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 <iostream>
#include <string>
#include <stack>
#include <queue>
using namespace std;
#define X first
#define Y second
int n, m, k; // 베추가 심어져있는 위치의 개수
int board[51][51];
bool vis[51][51];
int dx[4] = { 0, 1, 0 ,-1 };
int dy[4] = { 1, 0, -1 , 0 };
int testCase;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//시작점이 떨어져있는 경우.. 이중 for문.. 
	//board 필요, vis 필요 .. , dist는 불필요.. 상하좌우 필요.. 
	cin >> testCase; 
	while (testCase--) {
		cin >> m >> n >> k;
		for (int i = 0; i < n; i++) { // board, vis 초기화
			for (int j = 0; j < m; j++) {
				board[i][j] = 0;
				vis[i][j] = 0;
			}
		}
		while (k--) { // board 채우기
			int x, y;
			cin >> y >> x; //열에 해당 하는 값을 먼저 입력해준다.
			board[x][y] = 1; 
		}

		int cnt = 0; // cnt는 필요한 벌레의 수.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) { //이중for문으로 떨어져있는 시작점을 찾고 찾으면 bfs탐색
				if (vis[i][j] || board[i][j] == 0) continue;
				cnt++; //
				vis[i][j] = true;
				queue <pair <int, int >> q;
				q.push({ i,j });
				while (!q.empty()) {
					pair <int , int> cur = q.front();
					q.pop();
					for (int i = 0; i < 4; i++) {
						int nx = cur.X + dx[i];
						int ny = cur.Y + dy[i];
						if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
						if (vis[nx][ny] || board[nx][ny] == 0) continue; //이미 방문했거나배추가 없다면 넘긴다. 
						vis[nx][ny] = true;
						q.push({ nx, ny });
					}
				}
			}
		}
		cout << cnt << "\n";
	}
}

説明:

なお、「バンド」の問題では、行と列の入力順序が変更されています.
ベッツたちの位置は区域別に分かれている->2階建てのドアを使うべきだ.各領域はbfsによってナビゲートされる.