Sottomatrici

/* PROVA DI FONDAMENTI DI INFORMATICA 24.02.2016
 * TRACCIA C1
 *
 * Scrivere un programma C che letta da file una matrice di dimensione (n,m)
 * di interi positivi, individui la sottomatrice quadrata di ordine "o" la cui somma
 * degli elementi sulla diagonale principale è massima.
 * La sottomatrice individuata deve essere stampata su file di output insieme al
 * valore massimo calcolato.
 *
 * Un esempio di file di input e' il seguente:

  4   4
  3   1   2   1
  1   8   7   9
  4   7   8   7
  2   7   1   5

 Un esempio di esecuzione e':

 Digitare il nome del file contenente la matrice: input.txt

 Digita l'ordine della sottomatrice quadrata: 3

 Sottomatrice di ordine 3 con somma massima

 8   7   9
 7   8   7
 7   1   5

 Somma diagonale prinpipale: 21

 */

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

#define DIMR 20
#define DIMC 20
#define NCAR 100

/* Prototipi delle funzioni  */
FILE *ApriFile(char *);
void LeggiMatrice(FILE *, int [][DIMC], int *, int *);
int SommaSottoMatMax(int [][DIMC],int, int, int, int *, int *);
void ScriviSottoMatMax(FILE *, int [][DIMC], int, int, int, int);
void StampaMatrice(int [][DIMC], int, int);

/* Funzione main */
int main() {
    FILE *fp;
    int M[DIMR][DIMC];
    int r, c, ordine, x, y, max;

    /* Apre il file di input */
    fp = ApriFile("r");

    /* Legge la matrice da file */
    LeggiMatrice(fp, M, &r, &c);

    /* Chiude il file */
    fclose(fp);

    /* Stampa Matrice a video */
    StampaMatrice(M, r, c);

    printf("Digita l'ordine della sottomatrice quadrata: ");
    scanf("%d", &ordine);

    /* Calcola la sottomatrice di ordine "ordine" con diagonale principale massima */
    max = SommaSottoMatMax(M, r, c, ordine, &x, &y );
    printf("max: %d\n", max);
    if(max == -1)
        printf("Non esiste sottomatrice dell'ordine specificato.");
    else {
        /* stampa gli indici di inzio della sottomatrice */
        printf("indice riga: %d indice colonna: %d\n",x, y);

        /* Apre il file di output */
        fp = ApriFile("w");

        /* Stampa la sottomatrice e la somma della diagonale principale */
        ScriviSottoMatMax(fp, M, x, y, ordine, max);
        fclose(fp);
    }
    return (EXIT_SUCCESS);
}

/*
 La funzione ApriFile apre il file il cu nome e' fornito in input
 dall'utente nella modilità specificata dal parametro formale mode
 e ritorna il puntatore al file
 */
FILE *ApriFile(char* mode)
{
    FILE * fp;
    char filename[NCAR];
    printf("Insert %s filename: ", (mode[0]=='r')?("input"):("output"));
    scanf("%s", filename);
    if ((fp=fopen(filename, mode))==NULL)
        abort();
    else
        return fp;
}

/*
 La funzione LeggiMatrice riceve il puntatore al file di input, la matrice dove memorizzare
 i valori letti e 2 puntatori a intero per memorizzare le dimensioni delle matrice letta
 mediante passaggio per riferimento.
*/
void LeggiMatrice(FILE *fpin, int M[][DIMC], int *n, int *m )
{
    int i, j;
    fscanf(fpin, "%d %d", n, m);
    for(i=0;i<*n;i++)
        for(j=0;j<*n;j++)
            fscanf(fpin, "%d", &M[i][j]);
}

/*
 La funzione SommaSottoMatMax riceve come parametro la matrice e le sue dimensioni;
 l'ordine della sottomatrice quadrata da individuare e 2 puntatori a intero dove
 memorizzare le coordinate del punto iniziale della sottomatrice.
 Restituisce il valore della somma degli elementi della diagonale principale della
 sottomatrice individuata o "-1" in caso non esista una sottomatrice dell'ordine specificato.
 */
int SommaSottoMatMax(int M[][DIMC], int n, int m, int o, int *x, int *y ) {
    int i, j, k, sum, dmax=0;
    if ((n-o+1)*(m-o+1)<1)
        return -1;
    for(i=0;i<n-o+1;i++)
        for(j=0;j<m-o+1;j++){
            for(k=0, sum=0;k<o;k++)
                sum+=M[i+k][j+k];
            if(sum>dmax){
                dmax=sum;
                *x=i;
                *y=j;
            }
        }
    return dmax;
}

/*
 La funzione scriviSottoMatMax scrive su file di output la somma calcolata e la sottomatrice individuata.
 Riceve come parametri il puntatore al file di output, la matrice completa, le coordinate del punto di
 origine della sottomatrice individuata e il valore massimo. */
void ScriviSottoMatMax (FILE *fpout, int M[][DIMC], int x, int y, int o, int max)
{
    int i, j;
    fprintf(fpout, "Submatrix o-%d with max sum (%d)\n", o, max);
    for(i=0;i<o;i++)
        for(j=0;j<o;j++)
            fprintf(fpout, "%d%c", M[i+x][j+y], (j==(o-1))?('\n'):('\t'));
}

void StampaMatrice(int M[][DIMC], int r, int c)
{
    int i, j;

    for(i = 0; i < r; i++) {
    for(j = 0; j < c; j++) {
            printf("%d ", M[i][j]);
        }
        printf("\n");
    }
}