/**
 * @author Bruno Palma
 * Uma aplicacao que determina se um sistema fornecido pelo utilizador
 * e permeavel ou nao
 */

import java.util.Scanner;

public class Main {

	public static void main(String[] args){


        //informa o utilizador do funcionamento do programa


    		System.out.println("0 = no fechado");
        	System.out.println("1 = no aberto");

        //cria um scan ao System.in chamado sc

		Scanner sc = new Scanner(System.in);

		int[][] matriz;
		int dim;
	//le a dimensao do sistema

		System.out.println("Insira a dimensao do sistema: ");
		dim = leInteiroNoIntervalo(sc,1,1000);

		matriz = new int[dim][dim];


	//le a matriz
            for(int i=0; i<dim; i++){
                System.out.println("Linha " + (i+1));
                matriz[i] = leVector(sc,dim,0,1);
            }

            printMatriz(matriz);

            verSePermeavelVertical(matriz,dim);

            verSePermeavel(matriz,dim);


	}



        //               METODOS


	/**
	 *Le valor inteiro num intervalo dado
	 *@param sc - canal de leitura
	 *@param min - minimo admitido para o valor a ler
	 *@param max - maximo admitido para o valor a ler
	 *@return O numero lido
         */

	private static int leInteiroNoIntervalo(Scanner sc, int min, int max){
		int result = 0;
		do{
			result = sc.nextInt();
		}
		while (result < min || result > max);
		return result;
	}



	/**
	 * Le sequencia de inteiros que guarda num vector
	 * @param sc - canal de leitura
	 * @param dimensao - numero de inteiros a ler
	 * @param min - minimo admitido para os valores a ler
	 * @param max - maximo admitido para os valores a ler
	 * @return O vector com os numeros lidos
	 */

	private static int[] leVector(Scanner sc, int dimensao, int min,
                int max) {
            int[] result =  new int[dimensao];
            for (int i=0; i<result.length;i++){
                result[i]=leInteiroNoIntervalo(sc, min, max);
		}
            return result;
	}


	/**
	 * Imprime no ecra os elementos de uma matriz
	 * @param matriz -- a matriz a imprimir
	 * @requires matriz!=null && matriz matriz
	 */
	private static void printMatriz(int[][] matriz) {
		System.out.println("---------");
		for (int i=0; i<matriz.length; i++){
			for (int j=0; j<matriz[i].length; j++)
				System.out.print(" "+matriz[i][j]+" ");
			System.out.println();
		}
		System.out.println("---------");
	}








	/**
	 * Ve se uma matriz e permeavel na vertical e imprime a matriz inundada
	 * @param matriz -- a matriz a imprimir
	 * @param dimensao -- a dimensao do sistema
	 * @requires matriz!=null && matriz matriz && dimensao!=null
	 */

	private static void verSePermeavelVertical(int[][] matriz, int dimensao){

            int[][] vertical = new int[dimensao][dimensao];
            int[][] verticalaux = matriz;

//  copia os dados da primeira linha da matriz para a matriz inundada

            for(int i=0; i<dimensao; i++){
                vertical[0][i] = matriz[0][i];
            }

// inunda os pontos da matriz

            for(int i=0; i<dimensao-1; i++){
                for(int j=0; j<dimensao; j++){
                    if(vertical[i][j] == 1 && verticalaux[i+1][j] == 1)
            vertical[i+1][j] = 1;

                }
            }

// verifica se a matriz e permeavel ou nao

            for(int i=0;i<dimensao;i++){
                if(vertical[dimensao-1][i] == 1){
                    System.out.println("Sistema permeavel na vertical");
                    break;
                }
                else if((i == dimensao-1) && (vertical[dimensao-1][dimensao-1]==
                    0)){
                    System.out.println("Sistema impermeavel na vertical");
                }

            }

            printMatriz(vertical);
        }




	/**
         * Ve se uma matriz e permeavel e imprime a matriz inundada
         * @param aux -- copia da matriz dada
         * @param inundada -- matriz inundada
         * @requires aux!=null && aux matriz
	 */

        private static void verSePermeavel(int[][] aux, int dimensao){
			int[][] inundada = new int [dimensao][dimensao];
// copia os dados da primeira linha da matriz para a matriz inundada

            for(int i=0; i<dimensao; i++)
			inundada[0][i] = aux[0][i];

            for(int i=0; i<dimensao; i++){
			for(int j=0;j<dimensao-1;j++){

// verifica recursivamente se existem pontos inundaveis abaixo e a direita de
// um dado ponto inundado, da esquerda para a direita da matriz

				if(i!=dimensao-1){
                                    if(inundada[i][j]==1 && aux[i+1][j]==1)
							inundada[i+1][j] = 1;

                                    if(inundada[i][j]==1 && aux[i][(j+1)]==1)
							inundada[i][(j+1)] = 1;
				}

// excepcao para a ultima linha, de modo a nao ultrapassar os limites da matriz

				else{
                                    if(inundada[i][j] == 1 && aux[i][j+1] == 1)
							inundada[i][j+1] = 1;
				}
			}
// verifica recursivamente se existem pontos inundaveis abaixo e a esquerda de
// um dado ponto inundado, da direita para a esquerda da matriz, de modo a
// inundar pontos que possam ter sido negligenciados pelo for anterior

			for(int j=(dimensao-1);j>=0;j--){
                            if (j<=(dimensao-1) && j>0){
                                if(i!=dimensao-1){
                                    if(inundada[i][j]==1 && aux[i][j-1]==1){
                                        inundada[i][j-1] = 1;
                                    }
                                    if(inundada[i][j]==1 && aux[i+1][j]==1){
                                        inundada[i+1][j] = 1;
                                    }
                                }
                                else{
                                    if (inundada[i][j]==1 && aux[i][j-1]==1)
                                        inundada[i][j-1] = 1;
					}
                            }
                            if (j==0 && i!=dimensao-1){
                                if(inundada[i][0]==1 && aux[i+1][0]==1)
                                    inundada[i+1][0] = 1;
                            }
			}
            }
// verifica se a matriz e permeavel ou nao

            for(int i=0;i<dimensao;i++){
                if(inundada[dimensao-1][i] == 1){
                    System.out.println("Sistema permeavel");
                    break;
	    	}
	    	else if((i == dimensao-1) && (inundada[dimensao-1][dimensao-1]
                        == 0)){
                    System.out.println("Sistema impermeavel");
	   	}

            }

            printMatriz(inundada);
	}

}