質問する

次世代農業従事者のハンナは、江原道高寒(カンウォンド・コ寒)地域で有機白菜を栽培することにした.白菜を農薬で栽培しなければ害虫から白菜を守ることが重要なので、ハンナは害虫防止に有効な白菜ミミズを購入することにした.このミミズは白菜の近くに生息し、害虫を捕食することで白菜を保護する.特に、ある白菜に白いミミズが住んでいれば、このミミズは隣の他の白菜に移動することができ、これらの白菜も害虫の保護を受けることができる.
(1つの白菜の上下左右4方向にもう1つの白菜がある場合は隣接とみなす)
ハンナが白菜を植える畑は平らではなく,白菜を植える場所はみなそろっている.白菜が集まっているところに白菜のミミズが1匹あればいいので、隣接する白菜がいくつか分布しているかを調べてみると、全部で何匹必要かがわかります.
例えば、白菜畑が以下のように構成されている場合、白菜ミミズは少なくとも5匹必要である.
(0は白菜を植えていない土地を表し、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)を与える.

しゅつりょく

各試験箱について、所望の最小白菜白ミミズ数を出力する.

に答える

この問題はdfsを用いて解決した.各テストボックスのようにwhileドアを回し、各テストボックスにn,m,kを入力し、白菜の場所をarr配列に格納します.
dfsを実行するとarr配列の1箇所でtrueを返しcount+1を行い、この部分の1を0に変更して再アクセスを回避します.

ソース

import java.util.*;

public class Main {
	public static int testcase, m, n, k;
	public static int[][] arr;

	public static boolean dfs(int x, int y) {
		if (x < 0 || x >= n || y < 0 || y >= m) {
			return false;
		}

		if (arr[x][y] == 1) {
			arr[x][y] = 0;

			dfs(x - 1, y);
			dfs(x + 1, y);
			dfs(x, y - 1);
			dfs(x, y + 1);

			return true;
		}

		return false;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		testcase = sc.nextInt();

		while (testcase-- > 0) {
			m = sc.nextInt();
			n = sc.nextInt();
			k = sc.nextInt();

			arr = new int[n][m];
			for (int i = 0; i < k; i++) {
				int y = sc.nextInt();
				int x = sc.nextInt();
				arr[x][y] = 1;
			}

			int count = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (dfs(i, j)) {
						count += 1;
					}
				}
			}

			System.out.println(count);
		}
	}

}