[Vari] Contest 5: Sottomatrici

[WarDuck]

Cmq non è un problema divisibile strettamente in più sottoproblemi, se abbiamo una matrice 1000*1000 e la dividiamo in 4 sottomatrici quadrate, elaborandone una per volta non possiamo risolvere il problema, perché mancano tutte le intersezioni tra le 4 matrici.

[Vincenzo1968]

Se per il C# ci vuole il rullo di tamburi, per il C occorre la banda al completo:

Versione C (senza parallelismo);


Versione C# (con parallelismo):


Meno di tre secondi contro i diciassette della versione C#(che una volta eseguita, mi rallenta il sistema e mi tocca riavviare )

La macchina è questa:

AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

e questo è il codice:

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

// http://www.hwupgrade.it/forum/showthread.php?t=1799059

#define BUFFER_SIZE 4096

typedef enum tagStati
{
	S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
	int **m;
	int side;
} Array;

typedef struct tagResult
{
	int row;
	int col;
	int size;
	int sum;
} Result;

int GetArraySize(const char *szFileName)
{
	int array_size;
	FILE *fp;
	char buffer[BUFFER_SIZE + 1];
	int numread;
	int k;
	char c;

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 4 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}
	*(buffer + numread + 1) = '\0';

	k = 0;
	c = *(buffer + k);
	array_size = 0;
	while ( c != '\n' )
	{
		if ( c >= '0' && c <= '9' )
		{
			array_size = array_size * 10 + c - '0';

		}
		c = *(buffer + k++);
	}

	fclose(fp);

	return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
	Stati stato = S0;
	FILE *fp;
	unsigned char buffer[BUFFER_SIZE + 1];
	int numblocks;
	int numread;
	char c;
	int k, x;
	int riga, colonna;
	int num;
	int segno;

	pArray->side = GetArraySize(szFileName);
	if ( pArray->side <= 0 )
	{
		printf("Errore nella lettura del file.\n");
		return S_ERROR;
	}

	pArray->m = (int**)malloc(sizeof(int*)* pArray->side);
	if ( pArray->m != NULL )
	{
		for ( x = 0; x < pArray->side; x++ )
		{
			pArray->m[x] = (int*)malloc(sizeof(int)* pArray->side);
			if ( pArray->m[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	if ( fseek(fp, 0, SEEK_END) )
		return 0;

	numblocks = ftell(fp)/BUFFER_SIZE;
	if ( numblocks == 0 )
	{
		numblocks = 1;
	}
	else
	{
		if ( ftell(fp) % BUFFER_SIZE != 0 )
			numblocks++;
	}

	fseek(fp, 0, SEEK_SET);
	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 1 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}

	k = 0;
	c = *(buffer + k++);
	while ( c != '\n' )
	{
		if (c == '\0')
		{
			printf("Errore 2 nella lettura del file.\n");
			fclose(fp);
			return S_ERROR;
		}
		c = *(buffer + k++);
	}

	riga = colonna = 0;
	num = 0;
	x = 0;
	while ( x < numblocks )
	{
		c = *(buffer + k++);

		switch ( stato )
		{
		case S0:
			segno = 1;
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				stato = S1;
			}
			else if ( c == '-' )
			{
				num = 0;
				stato = S2;
			}
			else if ( c == '\r' )
			{
			}
			else if ( c == '\n' )
			{
				colonna = 0;
				riga++;
				if (riga >= pArray->side)
					return stato;
			}
			else
			{
				printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
				return S_ERROR;
			}
			break;
		case S1:
			if ( c >= '0' && c <= '9' )
			{
				num = num * 10 + c - '0';
			}
			else if ( c == ' ' || c == '\r' || c == '\n' )
			{
				pArray->m[riga][colonna] = num * segno;
				num = 0;
				colonna++;
				stato = S0;
			}
			else 
			{
				printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		case S2:
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				segno = -1;
				stato = S1;
			}
			else 
			{
				printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		}

		if ( k >= BUFFER_SIZE )
		{
			numread = fread(buffer, 1, BUFFER_SIZE, fp);
			if (numread == 0)
			{
				fclose(fp);
				printf("Errore 3 nella lettura del file %s\n", szFileName);
				return S_ERROR;
			}
			k = 0;
			x++;
		}
	}

	fclose(fp);

	return stato;
}

int FindKadane(Array *pArray, Result *pRes)
{
	int *pr;

	int riga, colonna, dim, somma;

	int riga1, colonna1, dim1;
	int riga2, colonna2, dim2;

	int z, i, x, y, w;
    int t = 0;
    int S = 0, s = 0, k, l, x1 = 0, x2 = 0, y1 = 0, y2 = 0, j;

	pr = (int*)malloc(sizeof(int)*(pArray->side*pArray->side));
	if ( !pr )
	{
		printf("Memoria insufficiente.\n");
		return -1;
	}
 
    for( z = 0; z < pArray->side; z++ )
    {
        for( i = 0; i < pArray->side; i++ )
			pr[i] = 0;
 
		for( x = z; x < pArray->side; x++ )
        {
            t = 0;
            s = 0;
            j = 0;
            k = 0; l = 0;
            for( w = 0; w < pArray->side; w++ )
            {
				pr[w] = pr[w] + pArray->m[x][w];
                t = t + pr[w];
                if( t > s)
                {
                    s = t;
                    k = w;
                    l = j;
                }
                if( t < 0 )
                {
                    t = 0;
                    j = w + 1;
                }
            }
            if( s > S )
            {
				if ( z - x == l - k )
				{
					S = s;
					x1 = x;
					y1 = k;
					x2 = z;
					y2 = l;
				}
            }
        }
    }

	free(pr);

	pRes->row = x2;
	pRes->col = y2;
	pRes->size = x1 - x2 + 1;
	pRes->sum = S;

	somma = 0;

	riga1 = pRes->row - 5;
	if ( riga1 < 0 )
		riga1 = 0;
	riga2 = pRes->row + 5;
	if ( riga2 >= pArray->side )
		riga2 = pArray->side - 1;

	colonna1 = pRes->col - 5;
	if ( colonna1 < 0 )
		colonna1 = 0;
	colonna2 = pRes->col + 5;
	if ( colonna2 > pArray->side )
		colonna2 = pArray->side - 1;

	dim1 = pRes->size - 10;
	if ( dim1 < 1 )
		dim1 = 1;
	dim2 = pRes->size + 10;
	if ( dim2 > pArray->side )
		dim2 = pArray->side;
	
	for ( dim = dim1; dim <= dim2; dim++ )
	{
		for ( riga = riga1; riga <= riga2; riga++ )
		{
			for ( colonna = colonna1; colonna <= colonna2; colonna++ )
			{
				for( y = riga; y < riga + dim; y++ )
				{
					for( x = colonna; x < colonna + dim; x++ )
					{
						somma += pArray->m[y][x];
					}
				}

				if ( somma > pRes->sum )
				{
					pRes->sum = somma;
					pRes->row = riga;
					pRes->col = colonna;
					pRes->size = dim;
				}

				somma = 0;
			}
		}
	}

    return 0;
}

int main()
{
	clock_t c_start, c_end;
	Array a;
	Result res;
	Stati stato;

	char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1bis.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1tris.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix8.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix9.txt";

	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2bis.txt";

	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix3.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix5.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix6.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix7.txt";

	c_start = clock();
	stato = DFA(szFileName, &a);
	if ( stato == S_ERROR )
	{
		printf("L'automa ha restituito un errore.\n");
		return;
	}
	c_end = clock();
	printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	c_start = clock();
	FindKadane(&a, &res);
	c_end = clock();
	printf("\nRiga       -> %d\nColonna    -> %d\nDimensione -> %d\nSomma      -> %d\n", res.row, res.col, res.size, res.sum);
	//printf("\nRiga1       -> %d\nColonna1    -> %d\nRiga2       -> %d\nColonna2    -> %d\nDimensione -> %d\nSomma      -> %d\n", res.row1, res.col1, res.row2, res.col2, res.size, res.sum);
	printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	return 0;
}

Grazie di cuore al Sig. Kadane che, parecchi anni or sono, inventò l'algoritmo(complessità = O(m^2n)):

http://www.cosc.canterbury.ac.nz/tad...a/35950621.pdf

e tanti saluti e sono al C#

[Vincenzo1968]

Corretto un piccolo bug e migliorati leggermente i tempi(2.75 secondi):

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

#define BUFFER_SIZE 4096

typedef enum tagStati
{
	S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
	int **m;
	int side;
} Array;

typedef struct tagResult
{
	int row;
	int col;
	int size;
	int sum;
} Result;

int GetArraySize(const char *szFileName)
{
	int array_size;
	FILE *fp;
	char buffer[BUFFER_SIZE + 1];
	int numread;
	int k;
	char c;

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 4 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}
	*(buffer + numread + 1) = '\0';

	k = 0;
	c = *(buffer + k);
	array_size = 0;
	while ( c != '\n' )
	{
		if ( c >= '0' && c <= '9' )
		{
			array_size = array_size * 10 + c - '0';

		}
		c = *(buffer + k++);
	}

	fclose(fp);

	return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
	Stati stato = S0;
	FILE *fp;
	unsigned char buffer[BUFFER_SIZE + 1];
	int numblocks;
	int numread;
	char c;
	int k, x;
	int riga, colonna;
	int num;
	int segno;

	pArray->side = GetArraySize(szFileName);
	if ( pArray->side <= 0 )
	{
		printf("Errore nella lettura del file.\n");
		return S_ERROR;
	}

	pArray->m = (int**)malloc(sizeof(int*)* pArray->side);
	if ( pArray->m != NULL )
	{
		for ( x = 0; x < pArray->side; x++ )
		{
			pArray->m[x] = (int*)malloc(sizeof(int)* pArray->side);
			if ( pArray->m[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	if ( fseek(fp, 0, SEEK_END) )
		return 0;

	numblocks = ftell(fp)/BUFFER_SIZE;
	if ( numblocks == 0 )
	{
		numblocks = 1;
	}
	else
	{
		if ( ftell(fp) % BUFFER_SIZE != 0 )
			numblocks++;
	}

	fseek(fp, 0, SEEK_SET);
	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 1 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}

	k = 0;
	c = *(buffer + k++);
	while ( c != '\n' )
	{
		if (c == '\0')
		{
			printf("Errore 2 nella lettura del file.\n");
			fclose(fp);
			return S_ERROR;
		}
		c = *(buffer + k++);
	}

	riga = colonna = 0;
	num = 0;
	x = 0;
	while ( x < numblocks )
	{
		c = *(buffer + k++);

		switch ( stato )
		{
		case S0:
			segno = 1;
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				stato = S1;
			}
			else if ( c == '-' )
			{
				num = 0;
				stato = S2;
			}
			else if ( c == '\r' )
			{
			}
			else if ( c == '\n' )
			{
				colonna = 0;
				riga++;
				if (riga >= pArray->side)
					return stato;
			}
			else
			{
				printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
				return S_ERROR;
			}
			break;
		case S1:
			if ( c >= '0' && c <= '9' )
			{
				num = num * 10 + c - '0';
			}
			else if ( c == ' ' || c == '\r' || c == '\n' )
			{
				pArray->m[riga][colonna] = num * segno;
				num = 0;
				colonna++;
				stato = S0;
			}
			else 
			{
				printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		case S2:
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				segno = -1;
				stato = S1;
			}
			else 
			{
				printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		}

		if ( k >= BUFFER_SIZE )
		{
			numread = fread(buffer, 1, BUFFER_SIZE, fp);
			if (numread == 0)
			{
				fclose(fp);
				printf("Errore 3 nella lettura del file %s\n", szFileName);
				return S_ERROR;
			}
			k = 0;
			x++;
		}
	}

	fclose(fp);

	return stato;
}

int FindKadane(Array *pArray, Result *pRes)
{
	int *pr;

	int riga, colonna, dim, somma;

	int riga1, colonna1, dim1;
	int riga2, colonna2, dim2;

	int z, i, x, y, w;
    int t = 0;
    int S = 0, s = 0, k, l, x1 = 0, x2 = 0, y1 = 0, y2 = 0, j;

	pr = (int*)malloc(sizeof(int)*pArray->side);
	if ( !pr )
	{
		printf("Memoria insufficiente.\n");
		return -1;
	}

	for( z = 0; z < pArray->side; z++ )
	{
		for( i = 0; i < pArray->side; i++ )
			pr[i] = 0;
 
		for( x = z; x < pArray->side; x++ )
		{
			t = 0;
			s = 0;
			j =	0;
			k = 0;
			l = 0;
			for( w = 0; w < pArray->side; w++ )
			{
				pr[w] = pr[w] + pArray->m[x][w];
				t = t + pr[w];
				if( t > s)
				{
					s = t;
					k = w;
					l = j;
				}
				if( t < 0 )
				{
					t = 0;
					j = w + 1;
				}
			}
			if( s > S )
			{
				if ( z - x == l - k )
				{
					S = s;
					x1 = x;
					y1 = k;
					x2 = z;
					y2 = l;
				}
			}
		}
	}

	free(pr);

	pRes->row = x2;
	pRes->col = y2;
	pRes->size = x1 - x2 + 1;
	pRes->sum = S;

	somma = 0;

	riga1 = pRes->row - 5;
	if ( riga1 < 0 )
		riga1 = 0;
	riga2 = pRes->row + 5;
	if ( riga2 >= pArray->side )
		riga2 = pArray->side - 1;

	colonna1 = pRes->col - 5;
	if ( colonna1 < 0 )
		colonna1 = 0;
	colonna2 = pRes->col + 5;
	if ( colonna2 >= pArray->side )
		colonna2 = pArray->side - 1;

	dim1 = pRes->size - 10;
	if ( dim1 < 1 )
		dim1 = 1;
	dim2 = pRes->size + 10;
	if ( dim2 > pArray->side )
		dim2 = pArray->side;

	for ( dim = dim1; dim <= dim2; dim++ )
	{
		for ( riga = riga1; riga <= riga2; riga++ )
		{
			if ( riga + dim > pArray->side )
				break;
			for ( colonna = colonna1; colonna <= colonna2; colonna++ )
			{
				if ( colonna + dim > pArray->side )
					break;
				for( y = riga; y < riga + dim; y++ )
				{
					for( x = colonna; x < colonna + dim; x++ )
					{
						somma += pArray->m[y][x];
					}
				}

				if ( somma > pRes->sum )
				{
					pRes->sum = somma;
					pRes->row = riga;
					pRes->col = colonna;
					pRes->size = dim;
				}

				somma = 0;
			}
		}
	}

    return 0;
}

int main()
{
	clock_t c_start, c_end;
	Array a;
	Result res;
	Stati stato;

	char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1bis.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1tris.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix8.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix9.txt";

	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2bis.txt";

	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix3.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix5.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix6.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix7.txt";

	c_start = clock();
	stato = DFA(szFileName, &a);
	if ( stato == S_ERROR )
	{
		printf("L'automa ha restituito un errore.\n");
		return;
	}
	c_end = clock();
	printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	c_start = clock();
	FindKadane(&a, &res);
	c_end = clock();
	printf("\nRiga       -> %d\nColonna    -> %d\nDimensione -> %d\nSomma      -> %d\n", res.row, res.col, res.size, res.sum);
	printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	return 0;
}

[marco.r]

deve avere altri bugs.
Cambiando qualche valore nella matrice da risultati sballati.

[Vincenzo1968]

Originariamente inviato da marco.r

deve avere altri bugs.
Cambiando qualche valore nella matrice da risultati sballati.

Dalle prove che ho fatto io non risultano. Puoi farmi qualche esempio?

Ciao

[marco.r]

Ho modificato un valore a caso della matrice, non so la posizione esatta per cui do il diff rispetto all'originale:

281c281
< 10 -5 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 -6 0 0 0 0 -7 0 0 0 0 0 10 1 0 0 0 0 0 0 -6 0 0 0 0 0 0 -9 0 0 -8 0 0 0 0 0 0 0 3 -2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -6 -2 0 0 0 0 0 6 0 0 0 0 -6 5 0 0 0 0 0 0 0 7 0 0 4 -5 -8 10 0 0 1 0 0 0 1 0 0 8 -4 -4 0 0 0 0 -7 0 0 0 0 0 -9 0 0 0 0 0 8 0 0 0 9 -8 9 4 0 0 -1 0 0 0 0 0 0 0 0 -10 0 0 -10 -10 0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 4 -9 -9 0 3 6 0 0 0 0 0 0 0 0 0 0 -2 0 0 2 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 -8 8 0 8 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 2 0 0 0 0 -4 0 0 0 6 0 0 8 0 0 0 0 0 0 0 0 7 5 3 0 0 0 -7 0 -8 0 0 0 0 0 -1 0 0 0 9 0 4 0 -4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 9 0 4 0 0 0 -9 0 10 0 0 0 0 0 0 0 0 6 0 2 0 0 -4 0 -6 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 0 7 0 0 5 0 -6 0 0 0 -7 0 0 0 0 0 0 0 5 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 5 0 0 0 -1 -4 0 0 -9 0 -3 0 0 0 -1 0 0 0 0 0 0 0 0 -3 0 0 0 -7 0 0 0 -9 0 -1 0 0 0 0 -7 0 2 0 -2 0 -2 -7 0 9 0 0 0 0 0 0 0 0 -3 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 10 0 -5 0 0 -9 0 0 -9 0 0 0 0 0 0 9 -8 -6 -5 0 0 -8 0 0 0 0 0 0 1 9 0 0 -8 0 0 0 0 0 0 0 0 0 4 0 0 0 -7 -10 0 0 6 0 0 -1 -7 0 -10 0 0 0 0 0 0 0 -4 -4 0 0 0 0 0 -4 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 3 0 3 0 0 -5 0 0 0 0 5 -9 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 5 0 0 0 -9 0 0 0 0 -8 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 -4 0 0 0 -7 0 8 0 0 -2 0 0 0 0 5 5 1 0 6 0 0 1 0 0 0 0 0 -9 0 10 0 0 0 0 0 0 0 0 0 -2 0 -4 0 0 0 0 2 0 0 0 0 0 10 0 0 0 -6 0 0 0 0 0 6 -10 0 0 0 0 0 -4 0 1 0 0 0 8 -5 2 0 0 0 0 0 -7 6 0 -8 0 0 0 0 0 0 0 0 2 0 0 0 -1 0 0 0 0 0 1 0 2 0 0 -1 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 -8 0 0 0 0 0 0 0 -8 9 0 0 0 0 0 4 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -6 3 0 8 0 -3 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 8 0 0 0 8 0 0 5 0 0 0 1 0 -10 0 0 0 0 0 -9 0 0 0 0 0 0 0 -10 0 0 -9 0 0 0 -5 0 0 0 4 0 -8 0 0 0 0 -3 0 0 1 0 0 0 0 0 0 10 0 -4 0 4 0 0 6 0 9 6 -3 0 0 0 -7 10 0 0 0 0 0 0 0 6 0 0 0 0 0 0 -4 0 0 0 0 -1 0 0 0 0 0 0 -7 0 0 0 0 0 -8 0 -9 -8 0 0 -3 0 2 0 0 0 0 -7 0 0 0 0 0 0 0 0 8 0 0 0 0 0 -1 0 6 0 0 0 0 0 0 0 0 0 0 -4 
---
> 10 -5 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 -6 0 0 0 0 -7 0 0 0 0 0 10 1 0 0 0 0 0 0 -6 0 0 0 0 0 0 -9 0 0 -8 0 0 0 0 0 0 0 3 -2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -6 -2 0 0 0 0 0 6 0 0 0 0 -6 5 0 0 0 0 0 0 0 7 0 0 4 -5 -8 10 0 0 1 0 0 0 1 0 0 8 -4 -4 0 0 0 0 -7 0 0 0 0 0 -9 0 0 0 0 0 8 0 0 0 9 -8 9 4 0 0 -1 0 0 0 0 0 0 0 0 -10 0 0 -10 -10 0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 4 -9 -9 0 3 6 0 0 0 0 0 0 0 0 0 0 -2 0 0 2 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 -8 8 0 8 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 2 0 0 0 0 -4 0 0 0 6 0 0 8 0 0 0 0 0 0 0 0 7 5 3 0 0 0 -7 0 -8 0 0 0 0 0 -1 0 0 0 9 0 4 0 -4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 9 0 4 0 0 0 -9 0 10 0 0 0 0 0 0 0 0 6 0 2 0 0 -4 0 -6 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 0 7 0 0 5 0 -6 0 0 0 -7 0 0 0 0 0 0 0 5 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 5 0 0 0 -1 -4 0 0 -9 0 -3 0 0 0 -1 0 0 0 0 0 0 0 0 -3 0 0 0 -7 0 0 0 -9 0 -1 0 0 0 0 -7 0 2 0 -2 0 -2 -7 0 9 0 0 0 0 0 0 0 0 -3 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 10 0 -5 0 0 -9 0 0 -9 0 0 0 0 0 0 9 -8 -6 -5 0 0 -8 0 0 0 0 0 0 1 9 0 0 -8 0 0 0 0 0 0 0 0 0 4 0 0 0 -7 -10 0 0 6 0 0 -1 -7 0 -10 0 0 0 0 0 0 0 -4 -4 0 0 0 0 0 -4 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 3 0 3 0 0 -5 0 0 0 0 5 -9 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 5 0 0 0 -9 0 0 0 1200 -8 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 -4 0 0 0 -7 0 8 0 0 -2 0 0 0 0 5 5 1 0 6 0 0 1 0 0 0 0 0 -9 0 10 0 0 0 0 0 0 0 0 0 -2 0 -4 0 0 0 0 2 0 0 0 0 0 10 0 0 0 -6 0 0 0 0 0 6 -10 0 0 0 0 0 -4 0 1 0 0 0 8 -5 2 0 0 0 0 0 -7 6 0 -8 0 0 0 0 0 0 0 0 2 0 0 0 -1 0 0 0 0 0 1 0 2 0 0 -1 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 -8 0 0 0 0 0 0 0 -8 9 0 0 0 0 0 4 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -6 3 0 8 0 -3 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 8 0 0 0 8 0 0 5 0 0 0 1 0 -10 0 0 0 0 0 -9 0 0 0 0 0 0 0 -10 0 0 -9 0 0 0 -5 0 0 0 4 0 -8 0 0 0 0 -3 0 0 1 0 0 0 0 0 0 10 0 -4 0 4 0 0 6 0 9 6 -3 0 0 0 -7 10 0 0 0 0 0 0 0 6 0 0 0 0 0 0 -4 0 0 0 0 -1 0 0 0 0 0 0 -7 0 0 0 0 0 -8 0 -9 -8 0 0 -3 0 2 0 0 0 0 -7 0 0 0 0 0 0 0 0 8 0 0 0 0 0 -1 0 6 0 0 0 0 0 0 0 0 0 0 -4

Se provo con il tuo codice mi da sempre il risultato iniziale.

Riga -> 565
Colonna -> 232
Dimensione -> 410
Somma -> 2419

Il conto non e' sbagliato, ma non e' il valore ottimale.
A me risulta che dovrebbe essere

Riga 198, colonna 212 dimensione 476 ed ottenere una somma di 2573.

Allego il codice che uso per verificare se il risultato ha valore corretto

#include <iostream>
#include <vector>
#include <iterator>
#include <fstream>

using namespace std;
struct Matrix
{
public:
    Matrix():_cols(0),_rows(0){}
    Matrix(const char* filename );
    Matrix(int rows, int cols );
    int& operator()(int row,int col);
    const int& operator()(int row,int col) const;
    int rows() const { return _rows; }
    int cols() const { return _cols; }
    Matrix& operator= ( const Matrix& m );
private:
    int _cols;
    int _rows;
    std::vector<int> matrix;
};



Matrix::Matrix( const char* filename )
{
    std::ifstream in(filename);
    string s;
    in >> s;
    s = s.substr( 2, s.size() - 4 );
    _cols = atoi( s.c_str() );
    _rows = _cols;
    matrix.resize( _rows*_cols );
    std::copy( istream_iterator<int>(in), istream_iterator<int>(), &matrix[0] );
}

Matrix::Matrix( int rows, int cols )
{
    _cols = cols;
    _rows = rows;
    matrix.resize( rows*cols, 0 );
}

Matrix& Matrix::operator=( const Matrix& m )
{
    if ( &m != this )
    {
        matrix.resize( m.matrix.size() );
        copy( m.matrix.begin(), m.matrix.end(), matrix.begin() );
        _rows = m._rows;
        _cols = m._cols;

    }
    
    return *this;
}


int& Matrix::operator()(int i, int j)
{
    return matrix[ i* _cols + j ];
}

const int& Matrix::operator()(int i, int j) const 
{
    return matrix[ i* _cols + j ];
}



int main(int argc, char** argv )
{
    if ( argc != 5 )
    {
        cout << "Usage: " << argv[0] << " matrix row col size" << endl;
        exit(1);
    }

    Matrix m(argv[1]);
    int start_row = atoi(argv[2]);
    int start_col = atoi(argv[3]);
    int size = atoi(argv[4]);
    int sum=0;
    for ( int i = start_row ; i < start_row+size ; ++i )
    {
        for ( int j= start_col ; j < start_col+size ; ++j )
        {
            sum+= m(i,j);
        }
    }
    cout << "The sum of the submatrix is " << sum << endl;
}

e una versione pseudo-becera dell'algoritmo di gugo che ho usato per calcolare il risultato ottimale (non avendo un compilatore C# sulla mia macchina).

#include <fstream>
#include <string>
#include <vector>
#include <iterator>
#include <iostream>
#include <time.h>
#include <sys/time.h>
#include <map>

using namespace std;


typedef int Size;
;
struct Matrix
{
    Matrix():_cols(0),_rows(0){}
    Matrix(const char* filename );
    Matrix(int rows, int cols );
    int& operator()(int row,int col);
    const int& operator()(int row,int col) const;
    int rows() const { return _rows; }
    int cols() const { return _cols; }
    Matrix& operator= ( const Matrix& m );
private:
    int _cols;
    int _rows;
    std::vector<int> matrix;
};

Matrix::Matrix( const char* filename )
{
    std::ifstream in(filename);
    string s;
    in >> s;
    s = s.substr( 2, s.size() - 4 );
    _cols = atoi( s.c_str() );
    _rows = _cols;
    matrix.resize( _rows*_cols );
    std::copy( istream_iterator<int>(in), istream_iterator<int>(), &matrix[0] );
}

Matrix::Matrix( int rows, int cols )
{
    _cols = cols;
    _rows = rows;
    matrix.resize( rows*cols, 0 );
}

Matrix& Matrix::operator=( const Matrix& m )
{
    if ( &m != this )
    {
        matrix.resize( m.matrix.size() );
        copy( m.matrix.begin(), m.matrix.end(), matrix.begin() );
        _rows = m._rows;
        _cols = m._cols;

    }
    
    return *this;
}


int& Matrix::operator()(int i, int j)
{
    return matrix[ i* _cols + j ];
}

const int& Matrix::operator()(int i, int j) const 
{
    return matrix[ i* _cols + j ];
}

typedef int Size;

Matrix calculate2x2Matrices( const Matrix& m )
{
    Matrix n( m.rows(), m.cols() );
    for ( int i=0; i+1 < m.rows() ; ++i )
    {
        for ( int j=0 ; j+1 < m.cols() ; ++j )
        {
            n(i,j) = m(i,j) + m(i+1,j) + m(i,j+1) + m(i+1,j+1);
        }
    }
    return n;
}

   

void solve( const Matrix& m, int& _bestRow, int& _bestCol, int& _bestSize, int& _bestValue )
{
    int bestRow, bestCol, bestSize, bestValue;
    bestRow = bestCol = 0;
    bestSize = 1;
    bestValue = m(0,0);

    map<Size,Matrix*> sums;
    sums[1] = new Matrix(m);
    sums[2] = new Matrix(calculate2x2Matrices(m));

    
    Matrix current_sums( m.rows(), m.cols() );

    for ( int size = 3; size <= m.rows() ; ++size )
    {
        if ( size % 10 == 0 )
            cerr << size << flush;
        else
            cerr << '.' << flush;

        int sizea = size/2;
        int sizeb = size - sizea;

        const Matrix& a = *sums[sizea];
        const Matrix& b = *sums[sizeb];

        
        for ( int i=0; i <= m.rows() - size  ; ++i )
        {
            for ( int j=0 ; j <= m.cols() - size ; ++j )
            {
                current_sums(i,j) = b(i,j) + a(i+sizeb,j) + a(i,j+sizeb) + b(i+sizea,j+sizea);
                
                if ( sizea != sizeb )
                    current_sums(i,j) -= m(i+sizea ,j+sizea);
                if ( current_sums(i,j) > bestValue )
                {
                    //                   cout << "good!" << i << ' ' << j << " " << size << ' ' << current_sums(i,j) << endl;
                    bestRow = i;
                    bestCol = j;
                    bestSize = size;
                    bestValue = current_sums(i,j);
                }
            }
        }
         if ( size <= m.rows()/2 )
             sums[size] = new Matrix(current_sums);
        for ( map<Size,Matrix*>::iterator i = sums.begin(); i != sums.end() ; ++i )
        {
            if ( i->first < size/2 )
            {
                delete i->second;
                sums.erase(i);
            }
            
        }
    }

    _bestRow = bestRow;
    _bestCol = bestCol;
    _bestSize = bestSize;
    _bestValue = bestValue;

}


double deltaTime()
{
    double d;
    struct timeval tv;
    static struct timeval lasttv = { 0 , 0 };
    if (lasttv.tv_usec == 0 && lasttv.tv_sec == 0)
        gettimeofday(&lasttv, NULL);
    gettimeofday(&tv, NULL);
    d = (tv.tv_usec - lasttv.tv_usec)/1000000.f
        + (tv.tv_sec - lasttv.tv_sec);
    lasttv = tv;
    return d;
}


int main(int argc, char** argv )
{
    string filename;
    if ( argc > 1 )
    {
        filename = argv[1];
    }
    else
    {
        filename = "matrix1.txt";
    }
    clock_t c_start, c_end;    
//    c_start = clock();
    deltaTime();
    Matrix m( argv[1] );
//    c_end = clock();
    //  float time = ((float)(c_end - c_start))/CLOCKS_PER_SEC;
    float time = deltaTime();
    printf("File read completed in %5.5f seconds\n", time);


    int row,col,size,value;
    c_start = clock();
    solve(m,row,col,size,value);
    c_end = clock();
    cout << "found solution in " << row << ' ' << col << " of size " << size << " and value " << value;
    time = ((float)(c_end - c_start))/CLOCKS_PER_SEC;
    printf(" in %5.5f seconds\n", time);
}

[Vincenzo1968]

Si, effettuando qualche altra prova ho verificato che il programma contiene ancora dei bug.

Il problema è che la versione originale dell'algoritmo di Kadane trova la sottomatrice rettangolare di somma massima.
Io ho cercato(senza riuscirci ) di adattarlo alla ricerca di sottomatrici quadrate.

Posto il codice con l'algoritmo originale(che, ripeto, trova la sottomatrice di somma massima rettangolare e non necessariamente quadrata). Se qualcuno vuole smanettarci un po'.

Sarebbe un peccato non riuscire ad adattarlo visti i tempi di esecuzione. La complessità è O(m^2 * n). Per m = n (come nel nostro caso), la complessità è, ovviamente, n^3.

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

#define BUFFER_SIZE 4096

typedef enum tagStati
{
	S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
	int **m;
	int side;
} Array;

typedef struct tagResult
{
	int row1;
	int col1;
	int row2;
	int col2;
	int sum;
} Result;

int GetArraySize(const char *szFileName)
{
	int array_size;
	FILE *fp;
	char buffer[BUFFER_SIZE + 1];
	int numread;
	int k;
	char c;

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 4 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}
	*(buffer + numread + 1) = '\0';

	k = 0;
	c = *(buffer + k);
	array_size = 0;
	while ( c != '\n' )
	{
		if ( c >= '0' && c <= '9' )
		{
			array_size = array_size * 10 + c - '0';

		}
		c = *(buffer + k++);
	}

	fclose(fp);

	return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
	Stati stato = S0;
	FILE *fp;
	unsigned char buffer[BUFFER_SIZE + 1];
	int numblocks;
	int numread;
	char c;
	int k, x;
	int riga, colonna;
	int num;
	int segno;

	pArray->side = GetArraySize(szFileName);
	if ( pArray->side <= 0 )
	{
		printf("Errore nella lettura del file.\n");
		return S_ERROR;
	}

	pArray->m = (int**)malloc(sizeof(int*)* pArray->side);
	if ( pArray->m != NULL )
	{
		for ( x = 0; x < pArray->side; x++ )
		{
			pArray->m[x] = (int*)malloc(sizeof(int)* pArray->side);
			if ( pArray->m[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	if ( fseek(fp, 0, SEEK_END) )
		return 0;

	numblocks = ftell(fp)/BUFFER_SIZE;
	if ( numblocks == 0 )
	{
		numblocks = 1;
	}
	else
	{
		if ( ftell(fp) % BUFFER_SIZE != 0 )
			numblocks++;
	}

	fseek(fp, 0, SEEK_SET);
	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 1 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}

	k = 0;
	c = *(buffer + k++);
	while ( c != '\n' )
	{
		if (c == '\0')
		{
			printf("Errore 2 nella lettura del file.\n");
			fclose(fp);
			return S_ERROR;
		}
		c = *(buffer + k++);
	}

	riga = colonna = 0;
	num = 0;
	x = 0;
	while ( x < numblocks )
	{
		c = *(buffer + k++);

		switch ( stato )
		{
		case S0:
			segno = 1;
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				stato = S1;
			}
			else if ( c == '-' )
			{
				num = 0;
				stato = S2;
			}
			else if ( c == '\r' )
			{
			}
			else if ( c == '\n' )
			{
				colonna = 0;
				riga++;
				if (riga >= pArray->side)
					return stato;
			}
			else
			{
				printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
				return S_ERROR;
			}
			break;
		case S1:
			if ( c >= '0' && c <= '9' )
			{
				num = num * 10 + c - '0';
			}
			else if ( c == ' ' || c == '\r' || c == '\n' )
			{
				pArray->m[riga][colonna] = num * segno;
				num = 0;
				colonna++;
				stato = S0;
			}
			else 
			{
				printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		case S2:
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				segno = -1;
				stato = S1;
			}
			else 
			{
				printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		}

		if ( k >= BUFFER_SIZE )
		{
			numread = fread(buffer, 1, BUFFER_SIZE, fp);
			if (numread == 0)
			{
				fclose(fp);
				printf("Errore 3 nella lettura del file %s\n", szFileName);
				return S_ERROR;
			}
			k = 0;
			x++;
		}
	}

	fclose(fp);

	return stato;
}

int FindKadane(Array *pArray, Result *pRes)
{
	int *pr;

	int z, i, x, w;
    int t = 0;
    int S = 0, s = 0, k, l, x1 = 0, x2 = 0, y1 = 0, y2 = 0, j;

	pr = (int*)malloc(sizeof(int)*pArray->side);
	if ( !pr )
	{
		printf("Memoria insufficiente.\n");
		return -1;
	}

	for( z = 0; z < pArray->side; z++ )
	{
		for( i = 0; i < pArray->side; i++ )
			pr[i] = 0;
 
		for( x = z; x < pArray->side; x++ )
		{
			t = 0;
			s = 0;
			j =	0;
			k = 0;
			l = 0;
			for( w = 0; w < pArray->side; w++ )
			{
				pr[w] = pr[w] + pArray->m[x][w];
				t = t + pr[w];
				if( t > s)
				{
					s = t;
					k = w;
					l = j;
				}
				if( t < 0 )
				{
					t = 0;
					j = w + 1;
				}
			}

			// riga       -> 138
			// colonna    -> 1
			// dimensione -> 751
			// somma      -> 7997600

			if( s > S )
			{
				S = s;
				x1 = x;
				y1 = k;
				x2 = z;
				y2 = l;
			}
		}
	}

	free(pr);

	pRes->row1 = x2;
	pRes->col1 = y2;
	pRes->row2 = x1;
	pRes->col2 = y1;
	pRes->sum = S;

    return 0;
}

int main()
{
	clock_t c_start, c_end;
	Array a;
	Result res;
	Stati stato;

	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1bis.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1tris.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix8.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix9.txt";

	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2bis.txt";

	char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix3.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix5.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix6.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix7.txt";

	c_start = clock();
	stato = DFA(szFileName, &a);
	if ( stato == S_ERROR )
	{
		printf("L'automa ha restituito un errore.\n");
		return;
	}
	c_end = clock();
	printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	c_start = clock();
	FindKadane(&a, &res);
	c_end = clock();
	printf("\nRiga1       -> %d\nColonna1    -> %d\nRiga2       -> %d\nColonna2    -> %d\nSomma       -> %d\n", res.row1, res.col1, res.row2, res.col2, res.sum);
	printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	return 0;
}

[Vincenzo1968]

Originariamente inviato da marco.r

...
Il conto non e' sbagliato, ma non e' il valore ottimale.
A me risulta che dovrebbe essere

Riga 198, colonna 212 dimensione 476 ed ottenere una somma di 2573.

Allego il codice che uso per verificare se il risultato ha valore corretto
...
e una versione pseudo-becera dell'algoritmo di gugo che ho usato per calcolare il risultato ottimale (non avendo un compilatore C# sulla mia macchina).
...

Io per verificare i risultati utilizzo il codice di Daniele che è risultato affidabilissimo.

[Vincenzo1968]

Penso di aver trovato la soluzione. Ho effettuato delle prove sul matricione e su un centinaio di piccoli file(matrici di dimensione 10x10), verificando i risultati col programma di Daniele.
I file di prova li creo con questo programmino:

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

int main()
{
	FILE *fp;
	char str[256];
	char strnum[256];
	char strFile[256];
	int i, j, k;
	int num;
	int m = 10, n = 10;
	int range_min = -100, range_max = 100;
	int numFiles = 100;

	srand( (unsigned)time( NULL ) );

	for ( k = 1; k < numFiles; k++ )
	{
		strcpy(strFile, "C:\\Temp\\Contest5\\Files\\MyMatrix");
		itoa(k, strnum, 10);
		if ( k <= 9 )
			strcat(strFile, "00");
		else if ( k > 9 && k < 100 )
			strcat(strFile, "0");
		strcat(strFile, strnum);
		strcat(strFile, ".txt");
		fp = fopen(strFile, "a");

		strcpy(str, "--10--\n");
		fwrite(str, strlen(str), 1, fp);

		for( i = 1; i <= m; i++ )
		{
			for( j = 1; j <= n; j++ )
			{
				num = (double)rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min;
				itoa(num, str, 10);
				strcat(str, " ");
				fwrite(str, strlen(str), 1, fp);
			}
			fwrite("\n", 1, 1, fp);
		}

		fclose(fp);

		printf("File %s\n", strFile);
	}

	return 0;
}

Prima di postare il codice voglio effettuare delle altre prove(almeno un migliaio) per essere sicuro al 100%.

[Vincenzo1968]

Il mio collega mi fa notare che, dal punto di vista pratico, è più utile trovare la sottomatrice rettangolare(che potrebbe anche essere quadrata).
Per esempio, nella manipolazione delle immagini, la sottomatrice rettangolare di somma massima rappresenta la cosidetta brightest part.
Un altro esempio è dato dalle statistiche nel campo socio-economico.

Per questi motivi posto la versione originale dell'algoritmo e tanti saluti e sono:

Questi i risultati sul matricione 1000x1000:


e questo è il codice:

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

#define BUFFER_SIZE 4096

typedef enum tagStati
{
	S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
	int **m;
	int side;
} Array;

typedef struct tagResult
{
	int row1;
	int col1;
	int row2;
	int col2;
	int sum;
} Result;

int GetArraySize(const char *szFileName)
{
	int array_size;
	FILE *fp;
	char buffer[BUFFER_SIZE + 1];
	int numread;
	int k;
	char c;

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 4 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}
	*(buffer + numread + 1) = '\0';

	k = 0;
	c = *(buffer + k);
	array_size = 0;
	while ( c != '\n' )
	{
		if ( c >= '0' && c <= '9' )
		{
			array_size = array_size * 10 + c - '0';

		}
		c = *(buffer + k++);
	}

	fclose(fp);

	return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
	Stati stato = S0;
	FILE *fp;
	unsigned char buffer[BUFFER_SIZE + 1];
	int numblocks;
	int numread;
	char c;
	int k, x;
	int riga, colonna;
	int num;
	int segno;

	pArray->side = GetArraySize(szFileName);
	if ( pArray->side <= 0 )
	{
		printf("Errore nella lettura del file.\n");
		return S_ERROR;
	}

	pArray->m = (int**)calloc(pArray->side + 1, sizeof(int*));
	if ( pArray->m != NULL )
	{
		for ( x = 0; x < pArray->side + 1; x++ )
		{
			pArray->m[x] = (int*)calloc(pArray->side + 1, sizeof(int));
			if ( pArray->m[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	if ( fseek(fp, 0, SEEK_END) )
		return 0;

	numblocks = ftell(fp)/BUFFER_SIZE;
	if ( numblocks == 0 )
	{
		numblocks = 1;
	}
	else
	{
		if ( ftell(fp) % BUFFER_SIZE != 0 )
			numblocks++;
	}

	fseek(fp, 0, SEEK_SET);
	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 1 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}

	k = 0;
	c = *(buffer + k++);
	while ( c != '\n' )
	{
		if (c == '\0')
		{
			printf("Errore 2 nella lettura del file.\n");
			fclose(fp);
			return S_ERROR;
		}
		c = *(buffer + k++);
	}

	riga = colonna = 0;
	num = 0;
	x = 0;
	while ( x < numblocks )
	{
		c = *(buffer + k++);

		switch ( stato )
		{
		case S0:
			segno = 1;
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				stato = S1;
			}
			else if ( c == '-' )
			{
				num = 0;
				stato = S2;
			}
			else if ( c == '\r' )
			{
			}
			else if ( c == '\n' )
			{
				colonna = 0;
				riga++;
				if (riga >= pArray->side)
					return stato;
			}
			else
			{
				printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
				return S_ERROR;
			}
			break;
		case S1:
			if ( c >= '0' && c <= '9' )
			{
				num = num * 10 + c - '0';
			}
			else if ( c == ' ' || c == '\r' || c == '\n' )
			{
				pArray->m[riga + 1][colonna + 1] = num * segno;
				num = 0;
				colonna++;
				stato = S0;
			}
			else 
			{
				printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		case S2:
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				segno = -1;
				stato = S1;
			}
			else 
			{
				printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		}

		if ( k >= BUFFER_SIZE )
		{
			numread = fread(buffer, 1, BUFFER_SIZE, fp);
			if (numread == 0)
			{
				fclose(fp);
				printf("Errore 3 nella lettura del file %s\n", szFileName);
				return S_ERROR;
			}
			k = 0;
			x++;
		}
	}

	fclose(fp);

	return stato;
}

int FindKadane(Array *pArray, Result *pRes)
{
	int Somma;
	int i,j,k,l,m,n,z,x,x1,x2,y1,y2,s,t;
	
	int **column;

	column = (int**)calloc(pArray->side + 1, sizeof(int*));
	if ( column != NULL )
	{
		for ( x = 0; x < pArray->side + 1; x++ )
		{
			column[x] = (int*)calloc(pArray->side + 1, sizeof(int));
			if ( column[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	m = pArray->side;
	n = pArray->side;

	x1 = 0; x2 = 0; y1 = 0; y2 = 0;
	Somma = -999999999;

	for( z = 1; z <= m; z++)
	{
		for( i = 1; i <= n; i++ )
			column[z - 1][i] = 0;

		for( x = z; x <= m; x++ )
		{
			t = 0;
			s = -999999999;
			k = 0;
			l = 0;
			j = 1;
			for( i = 1; i <= n; i++ )
			{
				column[x][i] = column[x - 1][i] + pArray->m[x][i];
				t = t + column[x][i];
				if(t > s)
				{
					s = t; k = i; l = j;
				}
				if( t < 0 )
				{
					t = 0;
					j = i + 1;
				}
			} 


			if( s > Somma )
			{
				Somma = s;
				x1 = x;
				y1 = k;
				x2 = z;
				y2 = l;
			}
		}
	}
	
	pRes->row1 = x2 - 1;
	pRes->col1 = y2 - 1;
	pRes->row2 = x1 - 1;
	pRes->col2 = y1 - 1;
	pRes->sum = Somma;

	return 0;
}


int main()
{
	clock_t c_start, c_end;
	Array a;
	Result res;
	Stati stato;

	char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";

	c_start = clock();
	stato = DFA(szFileName, &a);
	if ( stato == S_ERROR )
	{
		printf("L'automa ha restituito un errore.\n");
		return;
	}
	c_end = clock();
	printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	//printf("\n\npArray->m[1][1] -> %d\npArray->m[200][200] -> %d\n\n", a.m[1][1], a.m[200][200]);

	c_start = clock();
	FindKadane(&a, &res);
	c_end = clock();
	printf("\nRiga1       -> %d\nColonna1    -> %d\n\nRiga2       -> %d\nColonna2    -> %d\n\nSomma       -> %d\n\n", res.row1, res.col1, res.row2, res.col2, res.sum);
	printf("Tempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	return 0;
}

[Vincenzo1968]

E ci metto pure il carrico da undici:

AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

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

#define BUFFER_SIZE 4096

typedef enum tagStati
{
	S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
	int **m;
	int side;
} Array;

typedef struct tagResult
{
	int row1;
	int col1;
	int row2;
	int col2;
	int sum;
} Result;

int GetArraySize(const char *szFileName)
{
	int array_size;
	FILE *fp;
	char buffer[BUFFER_SIZE + 1];
	int numread;
	int k;
	char c;

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 4 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}
	*(buffer + numread + 1) = '\0';

	k = 0;
	c = *(buffer + k);
	array_size = 0;
	while ( c != '\n' )
	{
		if ( c >= '0' && c <= '9' )
		{
			array_size = array_size * 10 + c - '0';

		}
		c = *(buffer + k++);
	}

	fclose(fp);

	return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
	Stati stato = S0;
	FILE *fp;
	unsigned char buffer[BUFFER_SIZE + 1];
	int numblocks;
	int numread;
	char c;
	int k, x;
	int riga, colonna;
	int num;
	int segno;

	pArray->side = GetArraySize(szFileName);
	if ( pArray->side <= 0 )
	{
		printf("Errore nella lettura del file.\n");
		return S_ERROR;
	}

	pArray->m = (int**)calloc(pArray->side + 1, sizeof(int*));
	if ( pArray->m != NULL )
	{
		for ( x = 0; x < pArray->side + 1; x++ )
		{
			pArray->m[x] = (int*)calloc(pArray->side + 1, sizeof(int));
			if ( pArray->m[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	if ( fseek(fp, 0, SEEK_END) )
		return 0;

	numblocks = ftell(fp)/BUFFER_SIZE;
	if ( numblocks == 0 )
	{
		numblocks = 1;
	}
	else
	{
		if ( ftell(fp) % BUFFER_SIZE != 0 )
			numblocks++;
	}

	fseek(fp, 0, SEEK_SET);
	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 1 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}

	k = 0;
	c = *(buffer + k++);
	while ( c != '\n' )
	{
		if (c == '\0')
		{
			printf("Errore 2 nella lettura del file.\n");
			fclose(fp);
			return S_ERROR;
		}
		c = *(buffer + k++);
	}

	riga = colonna = 0;
	num = 0;
	x = 0;
	while ( x < numblocks )
	{
		c = *(buffer + k++);

		switch ( stato )
		{
		case S0:
			segno = 1;
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				stato = S1;
			}
			else if ( c == '-' )
			{
				num = 0;
				stato = S2;
			}
			else if ( c == '\r' )
			{
			}
			else if ( c == '\n' )
			{
				colonna = 0;
				riga++;
				if (riga >= pArray->side)
					return stato;
			}
			else
			{
				printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
				return S_ERROR;
			}
			break;
		case S1:
			if ( c >= '0' && c <= '9' )
			{
				num = num * 10 + c - '0';
			}
			else if ( c == ' ' || c == '\r' || c == '\n' )
			{
				pArray->m[riga + 1][colonna + 1] = num * segno;
				num = 0;
				colonna++;
				stato = S0;
			}
			else 
			{
				printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		case S2:
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				segno = -1;
				stato = S1;
			}
			else 
			{
				printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		}

		if ( k >= BUFFER_SIZE )
		{
			numread = fread(buffer, 1, BUFFER_SIZE, fp);
			if (numread == 0)
			{
				fclose(fp);
				printf("Errore 3 nella lettura del file %s\n", szFileName);
				return S_ERROR;
			}
			k = 0;
			x++;
		}
	}

	fclose(fp);

	return stato;
}

int FindKadaneSubCubic(Array *pArray, Result *pRes)
{
	int Somma;
	int i, j, k, l, m, n, kmin, x, z, x1, x2, y1, y2, s, t;
	int min_prefix;

	int **sum;
	int **column;

	column = (int**)calloc(pArray->side + 1, sizeof(int*));
	if ( column != NULL )
	{
		for ( x = 0; x < pArray->side + 1; x++ )
		{
			column[x] = (int*)calloc(pArray->side + 1, sizeof(int));
			if ( column[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	sum = (int**)calloc(pArray->side + 1, sizeof(int*));
	if ( sum != NULL )
	{
		for ( x = 0; x < pArray->side + 1; x++ )
		{
			sum[x] = (int*)calloc(pArray->side + 1, sizeof(int));
			if ( sum[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	m = pArray->side;
	n = pArray->side;

	for( i = 1; i <= m; i++ )
	{
		for( j = 1; j <= n; j++ )
		{
			column[i][j] = column[i - 1][j] + pArray->m[i][j];
			sum[i][j] = sum[i][j - 1] + column[i][j];
		}
	}

	x1 = 0; x2 = 0; y1 = 0; y2 = 0;
	Somma = -999999999;

	for( z = 1; z <= m; z++ )
	{
		for( i = 1; i <= n; i++)
			column[z - 1][i] = 0;

		for( x = z; x <= m; x++)
		{
			t = 0;
			s = -999999999;
			k = 0;
			l = 0;
			kmin = 0;
			min_prefix = 0;

			for( i = 1; i <= n; i++ )
			{
				t = sum[x][i] - sum[z - 1][i] - min_prefix;
				if( t > s )
				{
					s = t;
					k = kmin;
					l = i;
				}

				if( sum[x][i] - sum[z - 1][i] < min_prefix )
				{
					min_prefix = sum[x][i] - sum[z - 1][i];
					kmin = i;
				}
			}

			if( s > Somma )
			{
				Somma = s;
				x1 = x;
				y1 = l;
				x2 = z;
				y2 = k + 1;
			}
		}
	}

	for ( x = 0; x < pArray->side + 1; x++ )
		free(column[x]);
	free(column);

	for ( x = 0; x < pArray->side + 1; x++ )
		free(sum[x]);
	free(sum);

	pRes->row1 = x2 - 1;
	pRes->col1 = y2 - 1;
	pRes->row2 = x1 - 1;
	pRes->col2 = y1 - 1;
	pRes->sum = Somma;

	return 0;
}

int main()
{
	clock_t c_start, c_end;
	Array a;
	Result res;
	Stati stato;
	int x;

	char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";

	c_start = clock();
	stato = DFA(szFileName, &a);
	if ( stato == S_ERROR )
	{
		printf("L'automa ha restituito un errore.\n");
		return;
	}
	c_end = clock();
	printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	c_start = clock();
	FindKadaneSubCubic(&a, &res);
	c_end = clock();
	printf("\nRiga1       -> %d\nColonna1    -> %d\n\nRiga2       -> %d\nColonna2    -> %d\n\nSomma       -> %d\n\n", res.row1, res.col1, res.row2, res.col2, res.sum);
	printf("Tempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	for ( x = 0; x < a.side + 1; x++ )
		free(a.m[x]);
	free(a.m);

	return 0;
}

Grazie all'algoritmo ideato dai Sigg. Tamaki e Tokuyama, la complessità scende al di sotto di O(m^2 * n) e, quindi, nel caso m = n, sotto O(n^3).

[Vincenzo1968]

Ecco, dopo il millesimo test e controllando ogni volta il risultato sia col programma di Daniele che con quello di Gugo, la versione per la ricerca delle sottomatrici quadrate:

AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

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

#define BUFFER_SIZE 4096

typedef enum tagStati
{
	S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
	int **m;
	int side;
} Array;

typedef struct tagResult
{
	int row1;
	int col1;
	int row2;
	int col2;
	int sum;
} Result;

int GetArraySize(const char *szFileName)
{
	int array_size;
	FILE *fp;
	char buffer[BUFFER_SIZE + 1];
	int numread;
	int k;
	char c;

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 4 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}
	*(buffer + numread + 1) = '\0';

	k = 0;
	c = *(buffer + k);
	array_size = 0;
	while ( c != '\n' )
	{
		if ( c >= '0' && c <= '9' )
		{
			array_size = array_size * 10 + c - '0';

		}
		c = *(buffer + k++);
	}

	fclose(fp);

	return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
	Stati stato = S0;
	FILE *fp;
	unsigned char buffer[BUFFER_SIZE + 1];
	int numblocks;
	int numread;
	char c;
	int k, x;
	int riga, colonna;
	int num;
	int segno;

	pArray->side = GetArraySize(szFileName);
	if ( pArray->side <= 0 )
	{
		printf("Errore nella lettura del file.\n");
		return S_ERROR;
	}

	pArray->m = (int**)calloc(pArray->side + 1, sizeof(int*));
	if ( pArray->m != NULL )
	{
		for ( x = 0; x < pArray->side + 1; x++ )
		{
			pArray->m[x] = (int*)calloc(pArray->side + 1, sizeof(int));
			if ( pArray->m[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	if ( fseek(fp, 0, SEEK_END) )
		return 0;

	numblocks = ftell(fp)/BUFFER_SIZE;
	if ( numblocks == 0 )
	{
		numblocks = 1;
	}
	else
	{
		if ( ftell(fp) % BUFFER_SIZE != 0 )
			numblocks++;
	}

	fseek(fp, 0, SEEK_SET);
	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 1 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}

	k = 0;
	c = *(buffer + k++);
	while ( c != '\n' )
	{
		if (c == '\0')
		{
			printf("Errore 2 nella lettura del file.\n");
			fclose(fp);
			return S_ERROR;
		}
		c = *(buffer + k++);
	}

	riga = colonna = 0;
	num = 0;
	x = 0;
	while ( x < numblocks )
	{
		c = *(buffer + k++);

		switch ( stato )
		{
		case S0:
			segno = 1;
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				stato = S1;
			}
			else if ( c == '-' )
			{
				num = 0;
				stato = S2;
			}
			else if ( c == '\r' )
			{
			}
			else if ( c == '\n' )
			{
				colonna = 0;
				riga++;
				if (riga >= pArray->side)
					return stato;
			}
			else
			{
				printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
				return S_ERROR;
			}
			break;
		case S1:
			if ( c >= '0' && c <= '9' )
			{
				num = num * 10 + c - '0';
			}
			else if ( c == ' ' || c == '\r' || c == '\n' )
			{
				pArray->m[riga + 1][colonna + 1] = num * segno;
				num = 0;
				colonna++;
				stato = S0;
			}
			else 
			{
				printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		case S2:
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				segno = -1;
				stato = S1;
			}
			else 
			{
				printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		}

		if ( k >= BUFFER_SIZE )
		{
			numread = fread(buffer, 1, BUFFER_SIZE, fp);
			if (numread == 0)
			{
				fclose(fp);
				printf("Errore 3 nella lettura del file %s\n", szFileName);
				return S_ERROR;
			}
			k = 0;
			x++;
		}
	}

	fclose(fp);

	return stato;
}

int FindKadaneSquareSubmatrix(Array *pArray, Result *pRes)
{
	int Somma;
	int i, t, m, n, z, x, y, s;

	int riga, colonna, dim;
	
	int **column;

	column = (int**)calloc(pArray->side + 1, sizeof(int*));
	if ( column != NULL )
	{
		for ( x = 0; x < pArray->side + 1; x++ )
		{
			column[x] = (int*)calloc(pArray->side + 1, sizeof(int));
			if ( column[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	m = pArray->side;
	n = pArray->side;

	// somma dell'intero array
	Somma = 0;
	for( y = 1; y <= pArray->side; y++ )
	{
		for( x = 1; x <= pArray->side; x++ )  
		{
			Somma += pArray->m[y][x];
		}
	}

	pRes->sum = Somma;
	pRes->row1 = 1;
	pRes->col1 = 1;
	pRes->row2 = m;
	pRes->col2 = n;

	// singoli elememti
	for( y = 1; y <= pArray->side; y++ )
	{
		for( x = 1; x < pArray->side; x++ ) 
		{
			s = pArray->m[y][x];
			if ( s > Somma )
			{
				Somma = s;
				pRes->row1 = y;
				pRes->col1 = x;
				pRes->row2 = y;
				pRes->col2 = x;
			}							
		}
	}

	for ( z = 1; z <= m; z++ )
	{
		for ( i = 1; i <= n; i++ )
		{
			column[z][i] = column[z - 1][i] + pArray->m[z][i];
		}
	}

	s = 0;
	for ( dim = 2; dim <= pArray->side; dim++ )
	{
		for ( riga = 1; riga <= pArray->side - dim + 1; riga++ )
		{
			s = 0;
			for ( x = 1; x <= dim; x++ )
			{
				s += column[riga + dim - 1][x] - column[riga-1][x];
			}

			if ( s > Somma )
			{
				Somma = s;
				pRes->sum = s;
				pRes->row1 = riga;
				pRes->col1 = 1;
				pRes->row2 = dim + 1;
				pRes->col2 = dim + 1;
			}

			for ( colonna = x; colonna <= pArray->side; colonna++ )
			{

				t = column[riga + dim - 1][colonna - dim] - column[riga - 1][colonna - dim];
				s += column[riga + dim - 1][colonna] - column[riga-1][colonna];
				s -= t;

				if ( s > Somma )
				{
					Somma = s;
					pRes->sum = s;
					pRes->row1 = riga;
					pRes->col1 = colonna - dim + 1;
					pRes->row2 = riga + dim - 1;
					pRes->col2 = colonna;
				}
			}
		}
	}


	return 0;
}


int main()
{
	clock_t c_start, c_end;
	Array a;
	Result res;
	Stati stato;

	char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";

	c_start = clock();
	stato = DFA(szFileName, &a);
	if ( stato == S_ERROR )
	{
		printf("L'automa ha restituito un errore.\n");
		return;
	}
	c_end = clock();
	printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	c_start = clock();
	FindKadaneSquareSubmatrix(&a, &res);
	c_end = clock();
	printf("\nRiga1       -> %d\nColonna1    -> %d\n\nRiga2       -> %d\nColonna2    -> %d\n\nSomma       -> %d\n\n", res.row1, res.col1, res.row2, res.col2, res.sum);
	printf("Tempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	return 0;
}

[Vincenzo1968]

up