[伯俊-JAVA]DFS-Silver 2オーガニック白菜(1012)

質問する

に答える

import java.io.*;
import java.util.StringTokenizer;

public class BOJ_1012 {
	
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	
	static void func(int x, int y, int[][] map, boolean[][] visited) {
		visited[x][y] = true;
		
		for(int i = 0 ; i < 4; i++) {
			if(!visited[x + dx[i]][y + dy[i]] && map[x + dx[i]][y + dy[i]] == 1)
				func(x + dx[i], y + dy[i], map, visited);
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(in.readLine());
		
		for(int test = 0 ; test< T; test++) {
			st = new StringTokenizer(in.readLine());
			int M = Integer.parseInt(st.nextToken());
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			int[][] map = new int[N + 2][M + 2];
			boolean[][] visited = new boolean[N + 2][M + 2];
			int x;
			int y;
			for(int i = 0 ; i < K ; i++) {
				st = new StringTokenizer(in.readLine());
				x = Integer.parseInt(st.nextToken());
				y = Integer.parseInt(st.nextToken());
				map[y + 1][x + 1] = 1;
			}
			int count = 0;
			for(int i = 1 ; i <= N; i++) {
				for(int j = 1 ;j <= M ; j++) {
					if(map[i][j] == 1 && visited[i][j] == false) {
						func(i, j, map, visited);
						count++;
					}
				}
			}
			System.out.println(count);
		}
	}
}