Parition1 - NDDCoder

package ngay147;

import java.util.Scanner;

public class skyMap {
	
	static int N;
	static int[][] map;
	static int dx[] = {-1, 1, 0, 0};
	static int dy[] = {0, 0 , -1, 1};
	
	static int dfs(int i, int j) {
		if(i < 0 || i >= N | j < 0 || j >= N || map[i][j] == 0)
			return 0;
		map[i][j] = 0;
		int cnt = 1;
		
		for(int d = 0; d < 4; d++) {
			cnt += dfs(i+dx[d], j+dy[d]);
		}
		return cnt;
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int T = Integer.parseInt(sc.nextLine());
		
		while(T-- > 0) {
			N = Integer.parseInt(sc.nextLine());
			map = new int[N][N];;
			
			for(int i = 0; i < N; i++) {
				String[] row = sc.nextLine().split(" ");
				for(int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(row[j]);
				}
			}
			
			int constellationCount = 0;
			int maxStars = 0;
			
			for(int i = 0; i <  N; i++) {
				for(int j = 0; j < N; j++) {
					if(map[i][j] == 1) {
						int size = dfs(i, j);
						constellationCount++;
						if(size > maxStars) maxStars = size;
					}
				}
			}
			
			System.out.println(constellationCount + " " + maxStars);
		}
		
	}
}