//ESC101 : Fundamental of Computing
//Lab 9 for 23 October 2008

// Solution for Problem 2

/*Key Idea:  First generate the matrix using Random numbers. Then check for the reservoir with min height. we will mark the reservoir as holed. The checking for other connected holes is done as below
 *step1 : starting from beginning parse through entire array for holes
 *step2: if a hole found check the four neighbouring elements whether they are higher or lower, if heigher mark them as connected.
 *step3: while marking the higher ones set the boolean changed to true indicating there can be more connected reservoirs
 *ste4: In this way we iterate until there is no other reservoirs which can be marked. that is change is false.
 *step5: Then check for min in the rest of the unmarked reservoirs and repeat the above four steps untill every reservoir is marked.*/
 
 
import java.util.*;

class Reservoir{
	int noofres;
	int heights[][];
	boolean marked[][];
	int min;
	int min_i;
	int min_j;
	int holes[][];
	int noofholes;
	Reservoir(int num){
		noofres = num;
		noofholes = 0;
		heights = new int[num][num];
		marked = new boolean[num][num];
		holes = new int[num*num][2];
		for(int i=0;i<noofres;i++)
			for(int j=0;j<noofres;j++)
				marked[i][j] = false;
		Random r = new Random();
		for(int i=0;i<noofres;i++){
			for(int j=0;j<noofres;j++){
				int rand;
				while((rand = r.nextInt(100)) < 10);
				heights[i][j] = rand;
			}
		}
	}
	void printHeights(){
		for(int i=0;i<noofres;i++){
			for(int j=0;j<noofres;j++){
				System.out.print(heights[i][j] + "\t");
			}
			System.out.println();
		}
	}
	void findmin(){  //code for finding reservoir with minimum height*/
		min=1000;
		min_i=1000;
		min_j=1000;
		for(int i=0;i<noofres;i++){
			for(int j=0;j<noofres;j++){
				if(heights[i][j] < min && !marked[i][j]){
					min = heights[i][j];
					min_i = i;
					min_j = j;
				}
			}
		}
	}
	
	void calcRest(){  //code for finding the reservoirs connected to the given holed reservoir
		marked[min_i][min_j] = true;
		System.out.println("marking -> " + " "+ min_i+ " " + min_j);
		boolean change = true;
		while(change){
			change = false;
			for(int i=0;i<noofres;i++){
				for(int j=0;j<noofres;j++){
					if(marked[i][j]){
						if((i-1>=0) &&(marked[i-1][j]==false)&&(heights[i-1][j] > heights[i][j])){
							marked[i-1][j] = true;
							System.out.println("marking -> " + " "+ (i-1) + " " + j);
							change = true;
						}
						if((j-1>=0) &&(marked[i][j-1]==false)&&(heights[i][j-1] > heights[i][j])){
							marked[i][j-1] = true;
							System.out.println("marking -> " + " "+ i + " " + (j-1));
							change = true;
						}
						if((i+1<noofres) &&(marked[i+1][j]==false)&&(heights[i+1][j] > heights[i][j])){
							marked[i+1][j] = true;
							System.out.println("marking -> " + " "+ (i+1) + " " + j);
							change = true;
						}
						if((j+1<noofres) &&(marked[i][j+1]==false)&&(heights[i][j+1] > heights[i][j])){
							marked[i][j+1] = true;
							System.out.println("marking -> " + " "+ i + " " + (j+1));
							change = true;
						}
						
					}
				}
			}
		}
	}
	
	void putholes(){    //code for interating until there are no reservoir left unconnected to a hole
		boolean complete = false;
		while(!complete){
			complete = true;
			findmin();
			System.out.println("Hole is placed at " + min + " "+ min_i + " " + min_j);
			holes[noofholes][0] = min_i;
			holes[noofholes][1] = min_j;
			noofholes++;
			calcRest();
			for(int i=0;i<noofres;i++){
				for(int j=0;j<noofres;j++){
					if(!marked[i][j]){
						complete = false;
						break;
					}
				}
			}
		}	
	}
}

public class TestReservoir{
	public static void main(String args[]){
		int num = Integer.parseInt(args[0]);
		System.out.println(num);
		//int num = 15;
		Reservoir r = new Reservoir(num);
		r.printHeights();
		r.putholes();
		System.out.println("the no of holes required is  " + r.noofholes);
	}
}