(Programma C) Un quadrato nella matrice

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)