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];
                    }
		 
                }

            }        
                                                                
            clock.Stop();
            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();
        }
   
    }
}