using System;
using System.Diagnostics;
using System.IO;
using System.Linq;
//using System.Numerics;
namespace euler {
class Problem82 {
public static void Main(string[] args) {
new Problem82().Dynamic();
}
public void Dynamic(){
Stopwatch
clock = Stopwatch.
StartNew();
//int[,] grid = readInput(filename);
int[,] grid = new int[5,5] {{131,673,234,103,18},
{201,96,42,965,150},
{630,803,746,422,111},
{537,699,497,121,956},
{805,732,524,37,331}
};
int gridSize = 5;
int[] sol = new int[gridSize];
//initialise solution
for (int i = 0; i < gridSize; i++) {
sol[i] = grid[i, gridSize - 1];
}
for (int i = gridSize - 2; i >= 0; i--) {
// Traverse down
sol[0] += grid[0, i];
for (int j = 1; j < gridSize; j++) {
sol[j] = Math.Min(sol[j - 1] + grid[j, i], sol[j] + grid[j, i]);
}
//Traverse up
for (int j = gridSize - 2; j >= 0; j--) {
// sol[j] = Math.Min(sol[j], sol[j+1] + grid[j,i]);
// CHANGES MADE...
if(sol[j+1]==grid[j+1,i] + grid[j+1,i+1])
{
sol[j]=sol[j+1] + grid[j,i];
}
}
}
Console.WriteLine("In the {0}x{0} grid the min path is {1}", gridSize, sol.Min());
Console.
WriteLine("Solution took {0} ms", clock.
Elapsed.
TotalMilliseconds); }
private void printGrid(int[,] grid) {
int gridSize = grid.GetLength(0);
for (int k = 0; k < gridSize; k++) {
for (int j = 0; j < gridSize; j++) {
Console.Write(grid[k, j] + " ");
}
Console.WriteLine();
}
Console.WriteLine();
}
}
}
dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uRGlhZ25vc3RpY3M7CnVzaW5nIFN5c3RlbS5JTzsKdXNpbmcgU3lzdGVtLkxpbnE7CgovL3VzaW5nIFN5c3RlbS5OdW1lcmljczsKCm5hbWVzcGFjZSBldWxlciB7CiAgICBjbGFzcyBQcm9ibGVtODIgewoKICAgICAgICBwdWJsaWMgc3RhdGljIHZvaWQgTWFpbihzdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgICAgIG5ldyBQcm9ibGVtODIoKS5EeW5hbWljKCk7CiAgICAgICAgfQoKICAgICAgICBwdWJsaWMgdm9pZCBEeW5hbWljKCl7CgogICAgICAgICAgICBTdG9wd2F0Y2ggY2xvY2sgPSBTdG9wd2F0Y2guU3RhcnROZXcoKTsKCiAgICAgICAgICAgIC8vaW50WyxdIGdyaWQgPSByZWFkSW5wdXQoZmlsZW5hbWUpOwogICAgICAgICAgICAgIAogICAgICAgICAgICBpbnRbLF0gZ3JpZCA9IG5ldyBpbnRbNSw1XSB7ezEzMSw2NzMsMjM0LDEwMywxOH0sCgkJCQkJezIwMSw5Niw0Miw5NjUsMTUwfSwKCQkJCQl7NjMwLDgwMyw3NDYsNDIyLDExMX0sCgkJCQkJezUzNyw2OTksNDk3LDEyMSw5NTZ9LAoJCQkJCXs4MDUsNzMyLDUyNCwzNywzMzF9CgkJCQkJfTsKCQogICAgICAgICAgICBpbnQgZ3JpZFNpemUgPSA1OwogICAgICAgICAgICBpbnRbXSBzb2wgPSBuZXcgaW50W2dyaWRTaXplXTsKCiAgICAgICAgICAgIC8vaW5pdGlhbGlzZSBzb2x1dGlvbgogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGdyaWRTaXplOyBpKyspIHsKICAgICAgICAgICAgICAgIHNvbFtpXSA9IGdyaWRbaSwgZ3JpZFNpemUgLSAxXTsgICAgICAgICAgICAgICAgCiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGZvciAoaW50IGkgPSBncmlkU2l6ZSAtIDI7IGkgPj0gMDsgaS0tKSB7CiAgICAgICAgICAgICAgICAvLyBUcmF2ZXJzZSBkb3duCiAgICAgICAgICAgICAgICBzb2xbMF0gKz0gZ3JpZFswLCBpXTsKCiAgICAgICAgICAgICAgICBmb3IgKGludCBqID0gMTsgaiA8IGdyaWRTaXplOyBqKyspIHsKICAgICAgICAgICAgICAgICAgICBzb2xbal0gPSBNYXRoLk1pbihzb2xbaiAtIDFdICsgZ3JpZFtqLCBpXSwgc29sW2pdICsgZ3JpZFtqLCBpXSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIC8vVHJhdmVyc2UgdXAKICAgICAgICAgICAgICAgIGZvciAoaW50IGogPSBncmlkU2l6ZSAtIDI7IGogPj0gMDsgai0tKSB7CiAgICAgICAgICAgICAgICAgICAKCQkvLwkgc29sW2pdID0gTWF0aC5NaW4oc29sW2pdLCBzb2xbaisxXSArIGdyaWRbaixpXSk7CiAgICAgICAgICAgICAgICAgICAKCQkgICAvLyBDSEFOR0VTIE1BREUuLi4KICAgICAgICAgICAgICAgICAgICBpZihzb2xbaisxXT09Z3JpZFtqKzEsaV0gKyBncmlkW2orMSxpKzFdKQoJCSAgICB7CiAJCQlzb2xbal09c29sW2orMV0gKyBncmlkW2osaV07CiAgICAgICAgICAgICAgICAgICAgfQoJCSAKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgIH0gICAgICAgIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgIGNsb2NrLlN0b3AoKTsKICAgICAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUoIkluIHRoZSB7MH14ezB9IGdyaWQgdGhlIG1pbiBwYXRoIGlzIHsxfSIsIGdyaWRTaXplLCBzb2wuTWluKCkpOwogICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZSgiU29sdXRpb24gdG9vayB7MH0gbXMiLCBjbG9jay5FbGFwc2VkLlRvdGFsTWlsbGlzZWNvbmRzKTsKICAgICAgICB9CgoKICAgICAgICBwcml2YXRlIHZvaWQgcHJpbnRHcmlkKGludFssXSBncmlkKSB7CiAgICAgICAgICAgIGludCBncmlkU2l6ZSA9IGdyaWQuR2V0TGVuZ3RoKDApOwogICAgICAgICAgICAKICAgICAgICAgICAgZm9yIChpbnQgayA9IDA7IGsgPCBncmlkU2l6ZTsgaysrKSB7CiAgICAgICAgICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IGdyaWRTaXplOyBqKyspIHsKICAgICAgICAgICAgICAgICAgICBDb25zb2xlLldyaXRlKGdyaWRbaywgal0gKyAiICIpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUoKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZSgpOwogICAgICAgIH0KICAgCiAgICB9Cn0K