Connected

Connected.java

package puzzles;

import java.util.Scanner;

/*
 * 
 * 4
4
0 0 1 0
1 0 1 0
0 1 0 0
1 1 1 1
4
1 0 0 1
0 0 0 0
0 1 1 0
1 0 0 1
5
1 0 0 1 1
0 0 1 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0
8
0 0 1 0 0 1 0 0
1 0 0 0 0 0 0 1
0 0 1 0 0 1 0 1
0 1 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 1 1 0 1 1 0
1 0 1 1 0 1 1 0
0 0 0 0 0 0 0 0
 */


public class Connected {
	
	int noOfSets= 0;
	int[][] arr ;
	
	
	public void print(int[][] a){
		System.out.println("-----");
		for(int[] aa : a){
			for(int aaa : aa){
				System.out.print(aaa+" ");
			}
			System.out.println();
		}
	}

	public void solve(){
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		for(int x=0; x<N; x++){
			
			noOfSets = 0;
			int K = sc.nextInt();
			arr = new int[K][K];
			
			
			for(int i=0; i<K; i++){
				for(int j=0; j<K; j++){
					arr[i][j] = sc.nextInt();
				}
			}
			
			
			for(int i=0; i<K; i++){
				for(int j=0; j<K; j++){
					
					if(arr[i][j] == 1){
						dfs(i, j);
						noOfSets++;
						
						//print(arr);
						
					}
				}
			}
			
			System.out.println(noOfSets);
		}	
		
	}
	
	
	public void dfs(int i, int j){
		
		
		if(i<0 || j<0 || i>=arr.length || j>=arr[0].length || arr[i][j]==0)
			return;
			
		//print(arr);
		
		arr[i][j] =0;
		
		dfs(i+1, j);
		dfs(i, j+1);
		dfs(i-1, j);
		dfs(i, j-1);
		
		dfs(i-1, j-1);
		dfs(i-1, j+1);
		dfs(i+1, j-1);
		dfs(i+1, j+1);	
		
		
	}
	
	public static void main(String[] args) {
		new Connected().solve();
	}
	
	
}