(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 in input un file in questa forma

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

dove 5 è il numero di colonne(righe) della matrice n*n.

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,counter,tmp,isx,jsx;
	double squaroot; counter=0;
	text=fopen("input.txt","r");

    	if(text==NULL)
    	{
        	fprintf(stderr, "Invalid input.\n");
		exit(1);
    	}
	
	/*Leggo la dimensione n della matrice in input*/
    	fscanf(text,"%d",&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.*/
	squaroot=sqrt(counter);
	if(squaroot!=(int)squaroot)
	{
		printf("\nThere isn't any square.\n");
		exit(1);
	}

	/*Cerco il primo cancelletto,
	che sarà sicuramente il mio angolo 
	in alto a sinistra del 
	mio potenziale quadrato*/

	for(i=0;i<n;i++)
	{
       		 for(j=0;j<n;j++)
        	{
            		if(M[i][j]=='#')
            			goto final;
        	}
	}
	
	/*Valuto solo la parte di matrice 
	che inizia con il mio angolo sx
	, "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. */
	
	final:
	isx=i; jsx=j; tmp=counter;

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


	if(tmp==0)
	printf("\n\nThere is a square! :D\n\n");
	else
	printf("\n\nThere isn't any square!\n\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;
}