#include <stdio.h>
#include <stdlib.h>
#include <time.h>



int main()
{
    int i,j,k,n,l,i2,j2,sitio,groupn,p,sitioperco,npercol;  // Definção de variaveis
    srand(time(NULL));      //Comando utilizado para ser realmente randomico
    k = 2;                          //Numero do grupo
    npercol = 0;
    sitioperco = 0;
    p = 600;                     //Probabilidade de ser verdadeiro
    sitio = 0;                   //Numero de sitios ocupado
    n = 8;                     // tamanho da matriz quadrada
    int matriz[n+1][n+1];         // Definição da matriz quadrada
    for (i=0;i<n;i++)        //mudar as linhas
        for (j=0;j<n;j++)     //mudar as colunas
            {
            matriz[i][j] = rand() % 1001;  //Alimentando a matriz com os numeros aleatorios
                if(matriz[i][j] < p)        //Vendo se surgira uma passagem ou não
                {

                    matriz[i][j] = 1;   //Tem um sitio ocupado
                }
                else
                    matriz [i][j] = 0;   //Não tem sitio ocupado
            }
    matriz [0][0] = 0;

    for (j=0;j<n+1;j++){
        matriz [j][n+1] = 0;
    }
    for (j=0;j<n+1;j++){
        matriz [n+1][j] = 0;
    }
    for (i=1;i<n;i++){
        for (j=1;j<n;j++){
            if (matriz [i][j] == 1)
            {
                sitio = sitio +1;
            }
        }
    }
    printf("numero de sitios ocupados:%.2d\n",sitio);   // imprime o numero de sitios ocupados
    k = 1;
  /*  for (i=0;i<n+1;i++){
        for (j=0;j<n+1;j++)
            {
            printf ("(%d)",matriz[i][j]);
            }
        printf("\n");
    } */
    for (i=1;i<n+1;i++){
        for (j=1;j<n+1;j++){
            if (matriz [i][j] == 1)
            {
                matriz [i][j] = k;

            }

           /* if (matriz [0][j] == 1){
                matriz [0][j] = k+1;
            }*/
            else{
                k = k+1;
                matriz [i][j] = 0;
            }

        }
    }
 /* printf(" \n matriz \n");
  for (i=1;i<n;i++){
    for(j=1;j<n;j++){
        printf ("(%d)",matriz[i][j]);
    }
    printf ("\n");
  }
  printf ("nova matriz \n"); */
  for (i=1;i<n;i++){
    for(j=1;j<n;j++){
        if (matriz [i][j] != 0 && matriz [i+1][j] != 0){  // ta certo;(troca os numeros para baixo)
            for(i2=0;i2<n;i2++){
                for(j2=0;j2<n;j2++){
                    if(matriz [i2][j2] == matriz [i+1][j]){
                        matriz [i2][j2] = matriz [i][j];
                        matriz [i+1][j] = matriz [i][j];
                    }
                }
            }
        }
    }
  }
  /* for (i=1;i<n;i++){
     for (j=1;j<n;j++)
        {
        printf ("(%d)",matriz[i][j]);
        }
    printf("\n");
    } */
  for (j=1;j<n;j++){   // troca os numeros para direita
    for(i=1;i<n;i++){
        if (matriz [i][j] != 0 && matriz [i][j+1] != 0){
            for(i2=0;i2<n;i2++){
                for(j2=0;j2<n;j2++){
                    if(matriz [i2][j2] == matriz [i][j+1]){
                        matriz [i2][j2] = matriz [i][j];
                        matriz [i][j+1] = matriz [i][j];
                    }
                }
            }
        }
    }
  }
  /*printf ("\n pos primeira mudança \n");
  for (i=1;i<n;i++){
    for(j=1;j<n;j++){
        printf("(%d)",matriz[i][j]);
    }
    printf ("\n");
  } */
   for (i=1;i<n;i++){
      for(j=1;j<n;j++){
        if (matriz [i][j] != 0 && matriz [i+1][j] != 0){  // ta certo;(troca os numeros para baixo)
            for(i2=0;i2<n;i2++){
                for(j2=0;j2<n;j2++){
                    if(matriz [i2][j2] == matriz [i+1][j]){
                        matriz [i2][j2] = matriz [i][j];
                        matriz [i+1][j] = matriz [i][j];
                    }
                }
            }
        }
    }
  }
   for (j=1;j<n;j++){   // troca os numeros para direita
      for(i=1;i<n;i++){
        if (matriz [i][j] != 0 && matriz [i][j+1] != 0){
            for(i2=0;i2<n;i2++){
                for(j2=0;j2<n;j2++){
                    if(matriz [i2][j2] == matriz [i][j+1]){
                        matriz [i2][j2] = matriz [i][j];
                        matriz [i][j+1] = matriz [i][j];
                    }
                }
            }
        }
    }
  }
  printf ("\n pos primeira mudança \n");
  for (i=1;i<n;i++){
    for(j=1;j<n;j++){
        printf("(%d)",matriz[i][j]);
    }
    printf ("\n");
  }
  groupn = 0;
  for (l=1;l<k;l++){
        for (i=1;i<n;i++){
            for (j=1;j<n;j++){
                if((matriz [1][i] == l) && (matriz [n-1][j] == l)){
                    groupn = l;
                                }

                if ((matriz [i][1] == l) && (matriz [j][n-1] == l)){
                    groupn = l;
                                      }
                                    }
                            }
        if (groupn == l){
            for (i2=1;i2<n;i2++){
                for (j2=1;j2<n;j2++){
                    if (matriz[i2][j2] == groupn){
                        sitioperco = sitioperco +1;
                                             }
                                }
                        }
        }}

printf("\n %d",groupn);
if (groupn !=0 ){
        npercol = npercol +1;
}
printf ("\n %d",npercol);
printf ("\n %d",sitioperco);
    return 0;
}