Riduzione codice e tempi.
Toglo Eratostene, tolgo molti if e aggiusto output.
Mi sa che se non riesco a passare a qualche greedy decente finisco qui.
Codice:
Coordinate: 94,60 - Dimensione 56 - Somma 3185
Time: 297ms
Test: 3185
Codice:
class Program
{
static void Main(string[] args)
{
Matrix mat = new Matrix("Matrix2.txt");
Stopwatch sw = new Stopwatch();
sw.Start();
var toprint = mat.Ex7();
sw.Stop();
int x = toprint.Coords.x;
int y = toprint.Coords.y;
int z = toprint.Coords.z;
Console.WriteLine("Coordinate: {0},{1} - Dimensione {2} - Somma {3}", x, y, z, toprint.val);
Console.WriteLine("Time: {0}ms", sw.ElapsedMilliseconds);
int test = mat.Test(x, y, z);
Console.WriteLine("Test: {0}", test);
Console.ReadKey();
}
}
public class Matrix
{
public int Dim;
public int[,] Mat;
public void Save(string fname)
{
StreamWriter sw = new StreamWriter(@"C:\temp\" + fname);
sw.WriteLine("--{0}--", Dim);
for (int y = 0; y < Dim; y++)
{
for (int x = 0; x < Dim; x++)
{
sw.Write("{0} ", Mat[x, y].ToString());
}
sw.WriteLine();
}
sw.Close();
}
public Matrix(string fname)
{
Load(fname);
}
public Matrix(int[,] vals)
{
Mat = vals;
Dim = vals.GetLength(0);
}
public void Load(string fname)
{
StreamReader sr = new StreamReader(@"C:\temp\" + fname);
string fline = sr.ReadLine();
string mds = fline.Substring(2, fline.Length - 4);
Dim = int.Parse(mds);
Mat = new int[Dim, Dim];
for (int y = 0; y < Dim; y++)
{
string line = sr.ReadLine();
string[] valss = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
var valis = valss.Select(t => int.Parse(t)).ToArray();
Enumerable.Range(0, Dim).ForAll(x => Mat[x, y] = valis[x]);
}
sr.Close();
}
public struct CoordsStruct
{
public int x;
public int y;
public int z;
public CoordsStruct(int ix, int iy, int iz)
{
x = ix;
y = iy;
z = iz;
}
}
public struct Ex2Result
{
public CoordsStruct Coords;
public int val;
public Ex2Result(CoordsStruct ics,int ival)
{
Coords = ics;
val = ival;
}
}
public int Test(int x, int y, int d)
{
var dom = from ty in Enumerable.Range(y, d)
from tx in Enumerable.Range(x, d)
select Mat[tx, ty];
return dom.Sum();
}
public Ex2Result Ex7()
{
int[,][] Compl = new int[Dim, Dim][];
for (int y = 0; y < Dim; y++)
{
for (int x = 0; x < Dim; x++)
{
int mxy = (Dim+1) - ((x > y) ? x : y);
int[] st = Compl[x, y] = new int[mxy];
st[1] = Mat[x, y];
if (mxy > 2) st[2] = Mat[x, y] + Mat[x, y + 1] + Mat[x + 1, y] + Mat[x + 1, y + 1];
if (mxy > 3) st[3] = st[2] + Mat[x, y + 2] + Mat[x + 1, y + 2] + Mat[x + 2, y + 2] + Mat[x + 2, y + 1] + Mat[x + 2, y];
}
}
Ex2Result rer = new Ex2Result();
int rerval = int.MinValue;
for (int z = 4; z <= Dim; z++)
{
int mda = (z >> 1);
int ze1 = z & 1;
int md = mda + ze1;
bool ze1u1 = ze1 == 1;
int dimmz = Dim - z;
for (int y = 0; y < dimmz; y++)
{
for (int x = 0; x < dimmz; x++)
{
int xmda = x + mda;
int ymda = y + mda;
int cur = Compl[x, y][md]
+ Compl[x, y + md][mda]
+ Compl[x + md, y][mda]
+ Compl[xmda, ymda][md];
if (ze1u1)
{
cur -= Mat[xmda, ymda];
}
Compl[x, y][z] = cur;
if (cur > rerval)
{
rer = new Ex2Result(new CoordsStruct(x, y, z), cur);
rerval = cur;
}
}
}
}
return rer;
}}