(Programma C) Un quadrato nella matrice

Soluzione di LorenzoV

Questo è un problema uscito per le fasi di qualificazione della Facebook Hacker Cup 2014. Il codice sorgente del programma di seguito riportato è in grado di riconoscere se in una matrice quadrata è presente un quadrato "pieno": il programma accetta in input un file come da esempio:

5
4
..##
..##
....
....
4
..##
..##
#...
....
4
####
#..#
#..#
####
5
#####
#####
#####
#####
.....
5
#####
#####
#####
#####
#####

Dove il primo intero T indica il numero di casi (o test) e gli altri interi n indicano la grandezza di ogni matrice nxn.
Valgono i seguenti vincoli:
1 ≤ T ≤ 20
1 ≤ N ≤ 20
Seguendo questo esempio, in output il programma stamperà le seguenti righe:

Case #1: YES
Case #2: NO
Case #3: NO
Case #4: NO
Case #5: YES

La matrice n. 2 contiene un # fuori dal quadrato, la matrice n. 3 contiene un quadrato non riempito e la matrice n. 4 contiene un rettangolo.
Ecco il codice della mia soluzione:

#include <stdio.h>

typedef struct coordinate{
    int x;
    int y;
}coord;

int max(int x, int y){
    if (x>y) return x;
    else return y;
}

int min(int x, int y){
    if (x<y) return x;
    else return y;
}

int main(int argc, char *argv[]){
	FILE *fin;
	const int N=20;
	int i, j, k, h, n, T, M[N][N];
	int acase, find;
	coord asx, adx, bsx, bdx;
	char str[N];
	fin = fopen("input.txt","r");
	if (fin == NULL){
		fprintf(stderr, "Error opening file\n");
		exit(1);
	}
	fscanf(fin, "%d", &T);
	if (T>20 || T<1){
		fprintf(stderr, "Number of test cases not valid\n");
		exit(1);
	}
	for (k=0; k<T; k++){
        fscanf(fin, "%d", &n);
        if (n>N){
            fprintf(stderr, "Number of cells too high\n");
            exit(1);
        }
        for (i=0; i<n; i++){
            fscanf(fin, "%s", &str);
            for (j=0; j<n; j++){
                M[i][j]=str[j];
            }
        }
        asx.x=asx.y=-1;
        adx.x=adx.y=-1;
        bsx.x=bsx.y=-1;
        bdx.x=bdx.y=-1;
        /*Angolo in alto a sinistra*/
        find=0;
        for (i=0; i<n; i++){
            for (j=0; j<n && !find; j++){
                if (M[i][j]=='#'){
                    asx.x=i;
                    asx.y=j;
                    find=1;
                }
            }
        }
        /*Angolo in alto a destra*/
        find=0;
        for (i=n; i>=0; i--){
            for (j=0; j<n && !find; j++){
                if (M[i][j]=='#'){
                    adx.x=i;
                    adx.y=j;
                    find=1;
                }
            }
        }
        /*Angolo in basso a sinistra*/
        find=0;
        for (i=0; i<n; i++){
            for (j=n; j>=0 && !find; j--){
                if (M[i][j]=='#'){
                    bsx.x=i;
                    bsx.y=j;
                    find=1;
                }
            }
        }
        /*Angolo in basso a destra*/
        find=0;
        for (i=n; i>=0; i--){
            for (j=n; j>=0 && !find; j--){
                if (M[i][j]=='#'){
                    bdx.x=i;
                    bdx.y=j;
                    find=1;
                }
            }
        }
        /*Verifico che non sia un rettangolo*/
        acase=1;
        if (max(bsx.x, bdx.x)-min(asx.x, adx.x)!=max(bsx.y, bdx.y)-min(asx.y, adx.y)){
            acase=0;
        } else {
            /*Verifico se il quadrato è pieno*/
            for (i=min(asx.x, adx.x); i<=max(bsx.x, bdx.x); i++){
                for (j=min(asx.y, adx.y); j<=max(bsx.y, bdx.y); j++){
                    if (M[i][j]!='#'){
                        acase=0;
                    }
                }
            }
        }
        if (acase) printf("Case #%i: YES\n", k+1);
        else printf("Case #%i: NO\n", k+1);
	}
	fclose(fin);
	return 0;
}

--LorenzoV (talk) 17:25, 1 November 2014 (CET)

Soluzione di Nat

Il codice che posto qui di seguito verifica che nella matrice presa in input da file ci sia un quadrato pieno, ma attraverso controlli diversi rispetto al codice precedente e con una matrice allocata dinamicamente (si possono passare in input matrici più grandi di 20*20). Il programma prende lo stesso input della consegna postata da LorenzoV.

Se compilate con gcc va aggiunto il flag -lm perchè con la libreria math.h (per la radice quadrata) ci sono problemi.
Es. gcc main.c -o programma -lm

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

int main()
{
    	FILE *text; 
    	int n,i,j,k,counter,tmp,isx,jsx,boole,cases; int* vect;
	double squaroot; ;cases=0;
	text=fopen("input.txt","r");

	
    	if(text==NULL)
    	{
        	fprintf(stderr, "Invalid input.\n");
		exit(1);
    	}
	
	/*Leggo il numero di casi*/
    	fscanf(text,"%d",&cases);
	if(cases<=0)
    	{
        	fprintf(stderr, "Invalid input.\n");
		exit(1);
    	}
	vect=malloc(cases*sizeof(int));
	printf("\nCases =%d\n",cases);

  for(k=0;k<cases;k++)
  {     
	
	 counter=0;

	/*Leggo la dimensione n della matrice in input*/
    	fscanf(text,"%d",&n);
    	printf("n=%d \n",n);

	/*Alloco una matrice M e un vettore r, che mi serve
	 per copiare l'input su M. 
	In seguito setto tutto con un '.'*/
    	char **M;
    	M=(char**)malloc(n * sizeof(char*));
    	for (i=0; i<n; ++i)
    	{M[i]=(char*)malloc(n * sizeof(char));}

    	char *r;
    	r=(char*)malloc(n*sizeof(char));
	
	for (i=0; i<n; ++i)
	{
		r[i]='.';
		for(j=0;j<n;j++)
			M[i][j]='.';
	}
	
	for (i=0; i<n; i++){
            fscanf(text, "%s", r);
            for (j=0; j<n; j++)
	               M[i][j]=r[j];          
	}
		
	/*Stampa matrice*/
	for (i=0; i<n; ++i)
	{
        	for (j=0; j<n; j++)
			printf("%c",M[i][j]);

		printf("\n");
	}

	/*Conto i cancelletti*/
	for (i=0; i<n; ++i)
	{
        	for (j=0; j<n; j++)
		{
			if(M[i][j]=='#')
			counter++;
		}
	}
	
	/*Logicamente si ha che se il numero 
	di cancelletti non è un numero quadrato
	allora la matrice non potrà mai contenere un quadrato pieno.*/

			/*Ho risolto il problema del "quadrato di lato 0"
			con un controllo sul counter dei cancelletti totali*/
	squaroot=sqrt(counter);

	if(squaroot!=(int)squaroot||counter<1)
	{
		printf("\nThere isn't any square.\n\n");
		vect[k]=0;
		goto final;
	}

	/*Cerco il primo cancelletto,
	che sarà sicuramente il mio angolo 
	in alto a sinistra del 
	mio potenziale quadrato*/
	
			/*Ho risolto il goto con una variabile 
			booleana che cambia valore nel momento
			in cui trovo il primo cancelletto.
			Uso il goto però per trattare l'errore  
			nel caso in cui	la radice del numero di 
			cancelletti non sia intera.*/

	boole=1;
	for(i=0;i<n&&boole;i++)
	{
       		 for(j=0;j<n&&boole;j++)
        	{
            		if(M[i][j]=='#')
            			boole=0;
        	}
	}
	
	/*Valuto solo la parte di matrice 
	che inizia con il mio angolo sx
	e "spazzolo" solo per la lunghezza 
	del mio lato(radice quadrata del numero di cancelletti)
	e scalo il numero dei cancelletti: se alla fine sono 0 vuol dire
	che nello spazio k*k (k<=n) ho trovato esattamente k*k cancelletti e non ce ne sono altri.
	Quindi è un quadrato pieno. */
	
			/*Ho risolto il segmentation fault controllando
			che la mia visita della matrice non esca dal range n 
			oltre che dal range del lato del quadrato. 
			Sottraggo 1 a i e j poichè nel momento in cui 
                        boole cambia valore i cicli incrementano di 1 gli indici.*/
	isx=i-1; jsx=j-1; tmp=counter;

	for(i=isx;i<(isx+(int)squaroot)&&i<n;i++)
	{
	        for(j=jsx;j<(jsx+(int)squaroot)&&j<n;j++)
	        {
	            if(M[i][j]=='#')
	            tmp--;
	        }
	}


	if(tmp==0)
	{printf("\nThere is a square! :D\n\n");
	vect[k]=1;}
	else
	{printf("\nThere isn't any square!\n\n");
	vect[k]=0;}
	
	final:

	free(M);
	free(r);
	
  }
	printf("\nSTOP\n");
	for(k=0;k<cases;k++)
	{
			
		printf("CASE #%d :" ,k+1);		
		if(vect[k]==1)
		printf("YES\n");
		else printf("NO\n");
	}
	fclose(text);
}

--Nat (talk) 18:05, 2 November 2014 (CET)

Soluzione di rd

Ho provato a risolvere il problema giocando con i bit. Il risultato e' riportato qui sotto.

E' compatto ma un po' contorto...

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

void error_n_die(char *s)
{
  fprintf(stderr,"Error %s\n",s);
  exit(1);
}

/* count the # of bits set to 1 in an unsigned int */
int countones(unsigned int x) {
  int count;
  for (count=0; x!= 0; x>>=1)
    count += x & 1;
  return count;
}

/* if there is one sequence of 1, return the length of that seq*/
int seqlen(unsigned int x) {
  while (x != 0 && (x & 1)==0)
    x >>= 1;
  return countones(x+1)==1?countones(x):0;
}

int isacube(FILE *fin)
{
  int dim,i,j;
  char line[20];
  unsigned int values,vsum,hsum;
  fscanf(fin,"%d",&dim);
  if (dim>20 || dim<1)
    error_n_die("invalid matrix size");
  for (i=values=hsum=vsum=0; i<dim; i++) {
    unsigned int bline;
    fscanf(fin,"%s",line);
    for (j=bline=0; j<dim; j++)
      bline = (bline << 1) | (line[j] == '#');
    values |= 1<<countones(bline);
    hsum = (hsum << 1) | (bline != 0);
    vsum |= bline;
  }
  values |= 1<<countones(vsum) | 1<<countones(hsum);
  values &= ~1;
  values |= 1<<seqlen(vsum) | 1<<seqlen(hsum);
  return countones(values) == 1;
}

int main(int argc, char *argv[])
{
  FILE *fin;
  int ncases;
  int i;
  
  if ((fin=fopen("input.txt","r")) == NULL)
    error_n_die("opening file");
  fscanf(fin,"%d",&ncases);
  if (ncases>20 || ncases<1) error_n_die("not valid # of cases");
  for (i=0;i<ncases;i++)
    printf("case #%d: %s\n",i,isacube(fin)?"YES":"NO");
  return 0;
}

Renzo (talk) 07:54, 4 November 2014 (CET)

Altre considerazioni e un'altra soluzione (rd)

(NB: le indicazioni in Bold text sono esercizi da svolgere qui sul blog.)

Ho riguardato i programmi proposti.

La soluzione di LorenzoV ha un problema. Lui cerca i quattro vertici e poi controlla che tutti gli elementi all'interno siano '#'. Se provate con questa configurazione:

5
.....
.###.
####.
.###.
.....

vi dice che e' un quadrato. Si potrebbe correggere il programma cambiando il modo per cercare i vertici... come?

 /*Angolo in alto a sinistra*/
        find=0;
        for (i=0; i<n; i++){
            for (j=0; j<n && !find; j++){
                if (M[i][j]=='#'){ // controllo per righe
                    asx.x=i;
                    asx.y=j;
                    find=1;
                }
            }
        }
        /*Angolo in alto a destra*/
        find=0;
        for (i=n-1; i>=0; i--){
            for (j=0; j<n && !find; j++){
                if (M[j][i]=='#'){ // scambio indici, controllo per colonne
                    adx.x=j;
                    adx.y=i;
                    find=1;
                }
            }
        }
        /*Angolo in basso a sinistra*/
        find=0;
        for (i=0; i<n; i++){
            for (j=n-1; j>=0 && !find; j--){
                if (M[j][i]=='#'){ // scambio indici, controllo per colonne
                    bsx.x=j;
                    bsx.y=i;
                    find=1;
                }
            }
        }
        /*Angolo in basso a destra*/
        find=0;
        for (i=n-1; i>=0; i--){
            for (j=n-1; j>=0 && !find; j--){ // controllo per righe
                if (M[i][j]=='#'){
                    bdx.x=i;
                    bdx.y=j;
                    find=1;
                }
            }
        }

Eddy (talk) 21:40 Monday, 10 November 2014 (CET)

La soluzione di Nat invece funziona dal punto di vista algoritmico. Lui controlla che il numero di # sia un quadrato perfetto N^2 e quindi controlla che a partire dal primo # che si incontra scandendo la matrice in senso lessicografico tutti gli elementi nel quadrato a destra e in basso di lato N siano '#'.

Pero'... con questa configurazione:

10
..........
..........
..........
..........
..........
..........
..........
.....#####
##########
##########

il risultato e': Segmentation fault. Perché?

Inoltre se si fornisce una matrice vuota come:

4
....
....
....
....

dice che c'e' un quadrato (che sarebbe coerente, e' un quadrato di dimensione 0, ma secondo me le specifiche indicando "pieno" vogliono escludere questo caso).

Ho poi un paio di commenti stilistici per Nat: la soluzione non rispetta le specifiche per il formato del file in input e usa un 'goto' non per casi di errore. Il suo problema era "rompere" il doppio ciclo: come si puo' fare?

Infine vi lascio questa altra soluzione. Non usa alcuna memorizzazione per la matrice, neanche per una singola riga. Calcola se ci sia o meno un quadrato durante la lettura carattere per carattere. Quindi anche se fosse data in input una matrice di un milione per un milione di elementi il programma userebbe sempre solo 8 interi.

Chi ne descrive il funzionamento?

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

void error_n_die(char *s)
{
  fprintf(stderr,"Error %s\n",s);
  exit(1);
}

void flushtonl(FILE *fin)
{
  int c;
  while ((c=fgetc(fin)) != '\n' && c!=EOF)
    ;
}

int isacube(FILE *fin)
{
  int dim,i,j,c;
  int mini,maxi,minj,maxj;
  fscanf(fin,"%d",&dim);
  flushtonl(fin);
  mini=maxi=minj=maxj=-1;
  for (i=0; i<dim+1; i++) {
    int n=0;
    for (j=0; j<dim+1; j++) {
      c=(i<dim && j<dim)?fgetc(fin):'.';
      if (mini<0) {
        if (c=='#') {
          if (minj<0) minj=j;
        } else {
          if (minj>=0) maxj=j-1,mini=i;
        }
      } else if (maxi<0) {
        if (c!='#' ^ (j < minj || j > maxj))
          if (c == '#' || j != minj)
            mini=maxi=minj=maxj=dim;
          else
            maxi=i-1;
      } else {
        if (c=='#')
          mini=maxi=minj=maxj=dim;
      }
    }
    if (i<dim) flushtonl(fin);
  }
  return maxj-minj == maxi-mini && mini>=0 && maxi<dim;
}

int main(int argc, char *argv[])
{
  FILE *fin;
  int ncases;
  int i;

  if ((fin=fopen("input.txt","r")) == NULL)
    error_n_die("opening file");
  fscanf(fin,"%d",&ncases);
  if (ncases>20 || ncases<1) error_n_die("not valid # of cases");
  for (i=0;i<ncases;i++)
    printf("case #%d: %s\n",i,isacube(fin)?"YES":"NO");
  return 0;
}

Renzo (talk) 12:45, 6 November 2014 (CET)

c'era un bug. Ho corretto il confronto di riga 36 da "if (c == '#')" a "if (c == '#' || j != minj)". Chi riesce a trovare il caso che non veniva correttamente riconosciuto? (spiegando il perché!)

Renzo (talk) 20:30, 6 November 2014 (CET)

Funzionamento

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

void error_n_die(char *s)
{
  fprintf(stderr,"Error %s\n",s);
  exit(1);
}

/* funzione che "si mangia" quel che resta della riga 
   per portare l'indicatore di posizione del file alla riga successiva */
void flushtonl(FILE *fin)
{
  int c;
  while ((c=fgetc(fin)) != '\n' && c!=EOF)
    ;
}

int isacube(FILE *fin)
{
  int dim,i,j,c;
/* rappresentano rispettivamente la prima riga, l'ultima riga, 
   prima colonna, ultima colonna del quadrato */

  int mini,maxi,minj,maxj;
  fscanf(fin,"%d",&dim);
  flushtonl(fin);
  mini=maxi=minj=maxj=-1;
  for (i=0; i<dim+1; i++) {
    int n=0; // credo sia superfluo
    for (j=0; j<dim+1; j++) {
      c=(i<dim && j<dim)?fgetc(fin):'.';

/* partendo da "in alto a sinistra" se non ho ancora trovato la prima riga */
      if (mini<0) {
        if (c=='#') {
          /* so che e` la prima colonna */
          if (minj<0) minj=j;
        } else {
          /* se sono qui, vuol dire che ho gia` trovato la prima colonna e c=='.'
             ho trovato l'ultima colonna (era la precedente) e setto prima riga */
          if (minj>=0) maxj=j-1,mini=i;
        }
     /* ho gia` trovato la prima riga, la prima colonna e l'ultima colonna
        mi manca solo l'ultima riga */
      } else if (maxi<0) {
        /* entrero` qui soltanto se:
           1. c=='.' e sono nel range delle colonne
           2. c=='#' e sono fuori dal range delle colonne */
        if (c!='#' ^ (j < minj || j > maxj))
          /* casi di errore:
             1. se c=='#' c'e` un '#' fuori dal quadrato
             2. e` stato aggiunto j != minj, poiche` non verrebbe riconosciuto 
                ##
                #.   */ 
          if (c == '#' || j != minj)
            mini=maxi=minj=maxj=dim;
          else
            maxi=i-1; // trovato ultima riga
      } else {
        /* trovato un "#" al di fuori del quadrato  */
        if (c=='#')
          mini=maxi=minj=maxj=dim;
      }
    }
    if (i<dim) flushtonl(fin);
  }
  /* controllo che le dimensioni siano stato rispettate */ 
  return maxj-minj == maxi-mini && mini>=0 && maxi<dim;
}

int main(int argc, char *argv[])
{
  FILE *fin;
  int ncases;
  int i;

  if ((fin=fopen("input.txt","r")) == NULL)
    error_n_die("opening file");
  fscanf(fin,"%d",&ncases);
  if (ncases>20 || ncases<1) error_n_die("not valid # of cases");
  for (i=0;i<ncases;i++)
    printf("case #%d: %s\n",i,isacube(fin)?"YES":"NO");
  return 0;
}

Eddy (talk) 23:15 Monday, 10 November 2014 (CET)