Sky Map

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.6 kB
5
Indexable
Never
Sky map
You are making “sky map” to represent constellation (group of starts) in the sky.
In each element, 1 means star, 0 means empty.
And in a constellation, each start should have at least one connection with others via left/right/up/bottom. 
If two starts are located via diagonal, then
the two stars are not connected (belong to different constellation.)
How many constellations are in your sky map, and what is the number of starts in the greatest constellation?
[Input]
There can be more than one test case in the input.
The first line has T, the number of test cases.
Then the totally T test cases are provided in the following lines (T<=10)
In each test case, the first line has an integer N(5 ≤ N ≤ 25), the size of map.
The map is a square, and is represented as N x N matrix.
For next N lines, each contains each raw of the matrix
[Output]
For each test case, you should print the number of constellation and the number of starts in the greatest constellation separated by blank.
[I/O Example]
Input
2
7
0 1 1 0 0 0 0
0 1 1 0 1 0 0
1 1 1 0 1 0 1
0 0 0 0 1 1 1
1 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 0 1 1 0 0
5
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
Output
4 8
1 3

###########################################
input
5
5
1 0 0 0 0
0 1 1 1 0
1 1 0 0 0
1 0 1 1 1
0 0 1 0 1
9
0 0 1 1 1 1 1 1 1
0 0 1 0 0 0 0 1 1
1 0 1 0 1 0 0 0 1
1 1 1 1 1 0 1 0 1
0 0 1 0 0 1 1 0 0
0 0 0 0 1 1 0 0 0
0 1 1 0 0 0 0 1 0
1 0 1 0 0 1 0 1 0
1 1 1 0 0 1 1 1 1
17
1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0
0 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0
0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0
1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1
0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0
0 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0
0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
7
0 1 1 0 0 0 0
0 1 1 0 1 0 0
1 1 1 0 1 0 1
0 0 0 0 1 1 1
1 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 0 1 1 0 0
5
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0



#######################################################3
code
package SkyMap;

import java.io.FileInputStream;
import java.util.Scanner;

public class skyMap {
	static int n;
	static int [][] map;
	static int [] dx = {0, 1, 0, -1};
	static int [] dy = {1, 0, -1, 0};
	static int count;
	static void move (int x, int y) {
		map[x][y] = 0;
		for (int i = 0; i < 4; i++) {
			int x1 = x + dx[i];
			int y1 = y + dy[i];
			if (x1 >= 0 && y1 >= 0 && x1 < n && y1 < n && map[x1][y1] == 1) {
				count ++;
				move (x1, y1);
			}
		}
	}
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("D://Trainee//SRV_training//src//SkyMap//sky.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++) {
			n = sc.nextInt();
			map = new int [n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			int a = 0;
			int max = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (map[i][j] == 1) {
						count = 0;
						move(i, j);
						a++;
						if (max < count) {
							max = count;
						}
					}
				}
			}
			System.out.println( a + " " + (max+1));
		}

	}
}