fork(1) download
copy 
  1. using System;
  2. using System.Diagnostics;
  3. using System.IO;
  4. using System.Linq;
  5.  
  6. //using System.Numerics;
  7.  
  8. namespace euler {
  9.     class Problem82 {
  10.  
  11.         public static void Main(string[] args) {
  12.             new Problem82().Dynamic();
  13.         }
  14.  
  15.         public void Dynamic(){
  16.  
  17.             Stopwatch clock = Stopwatch.StartNew();
  18.  
  19.             //int[,] grid = readInput(filename);
  20.  
  21.             int[,] grid = new int[5,5] {{131,673,234,103,18},
  22. 					{201,96,42,965,150},
  23. 					{630,803,746,422,111},
  24. 					{537,699,497,121,956},
  25. 					{805,732,524,37,331}
  26. 					};
  27.  
  28.             int gridSize = 5;
  29.             int[] sol = new int[gridSize];
  30.  
  31.             //initialise solution
  32.             for (int i = 0; i < gridSize; i++) {
  33.                 sol[i] = grid[i, gridSize - 1];                
  34.             }
  35.  
  36.             for (int i = gridSize - 2; i >= 0; i--) {
  37.                 // Traverse down
  38.                 sol[0] += grid[0, i];
  39.  
  40.                 for (int j = 1; j < gridSize; j++) {
  41.                     sol[j] = Math.Min(sol[j - 1] + grid[j, i], sol[j] + grid[j, i]);
  42.                 }
  43.  
  44.                 //Traverse up
  45.                 for (int j = gridSize - 2; j >= 0; j--) {
  46.  
  47. 		//	 sol[j] = Math.Min(sol[j], sol[j+1] + grid[j,i]);
  48.  
  49. 		   // CHANGES MADE...
  50.                     if(sol[j+1]==grid[j+1,i] + grid[j+1,i+1])
  51. 		    {
  52.  			sol[j]=sol[j+1] + grid[j,i];
  53.                     }
  54.  
  55.                 }
  56.  
  57.             }        
  58.  
  59.             clock.Stop();
  60.             Console.WriteLine("In the {0}x{0} grid the min path is {1}", gridSize, sol.Min());
  61.             Console.WriteLine("Solution took {0} ms", clock.Elapsed.TotalMilliseconds);
  62.         }
  63.  
  64.  
  65.         private void printGrid(int[,] grid) {
  66.             int gridSize = grid.GetLength(0);
  67.  
  68.             for (int k = 0; k < gridSize; k++) {
  69.                 for (int j = 0; j < gridSize; j++) {
  70.                     Console.Write(grid[k, j] + " ");
  71.                 }
  72.                 Console.WriteLine();
  73.             }
  74.             Console.WriteLine();
  75.         }
  76.  
  77.     }
  78. }
  79.  
Success #stdin #stdout 0.04s 37128KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
In the 5x5 grid the min path is 694
Solution took 0.4964 ms
https://ideone.com/k9aOr
language:
C# (gmcs 5.20.1)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!