Untitled

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{

    class Program
    {
        int width = 3;
        int height = 3;
        int min = 0;
        int max = 100;

        static void Main(string[] args)
        {
            //Punkt startowy;
            var p = new Program();
            p.Run();
        }
        int[,] CreateRandomMatrix(int width, int height, int min, int max)
        {
            var array = new int[width, height];
            var random = new Random();
            for (int x = 0; x < width; x++)
                for (int y = 0; y < height; y++)
                {
                    array[x, y] = random.Next() % (max-min)+min;
                }
            return array;
        }
        int CheckPath(int[,] matrix, bool[] path)
        {
            int x = 0; int y = height - 1;
            int result = -1;
            for (int i = 0; i < path.Length; i++)
            {
                result += matrix[x, y];
                if (path[i] == false) y--;
                else x++;
                if (x >= width || y >= height) return -1; //wyszlo poza macierz
            }
            return result;
        }
        public void Run()
        {

            var array = CreateRandomMatrix(width, height, min, max); //tworzenie losowej macierzy

            var watch = System.Diagnostics.Stopwatch.StartNew(); //tylko do pomiaru czasu
            Sum(array, 0, height-1, "", 0,""); //wywolanie rekurencji
            watch.Stop(); //koniec liczenia czasu

            string matrixString = "";
            for (int y = 0; y < height; y++)
            {
                for (int x = 0; x < width; x++)
                {
                    matrixString += array[x, y] + " ";
                }
                matrixString += "\n"; //tworzenie stringu do wypisania w celach diagnostycznych
            }


            Console.WriteLine(matrixString);
            Console.WriteLine("Najlepsza sciezka to " + winnerPath+" z suma "+ winnerSum);
            Console.WriteLine("Funkcja rekurencyjna wykonala sie " + evaluations + " razy, w czasie " + watch.Elapsed.TotalMilliseconds + " ms");
            Console.WriteLine("Zwycieska sciezka byla zastepowana " + winnerChanges + " razy");
            Console.WriteLine("Sekwencja " + winnerSequence + " razy");
            Console.ReadKey();
        }
        int winnerChanges;
        string winnerPath;
        int winnerSum = 1000000;
        int evaluations = 0;
        string winnerSequence;
        void Sum(int[,] matrix, int x, int y, string path, int sum, string seq)
        {
            evaluations++; //w celach diagnostycznych
            if (x >= width || sum > winnerSum || y < 0)
                return; // jesli wyszlo poza zakres, lub suma jest wieksza niz aktualna najlepsza, nie idziemy dalej
            sum += matrix[x, y];
            seq += matrix[x, y]+ "+";

            if (x == width - 1 && y == 0 && sum < winnerSum) //jesli sciezka doszla do celu i jest najlepsza, nalezy ja dopisac
            {
                winnerSum = sum;
                winnerPath = path;
                winnerChanges++; // w celach diagnostycznych
                winnerSequence = seq;
            }
            Sum(matrix, x + 1, y, path + "1", sum, seq); //funkcja rekurencyjna stworzy dwie odnogi
            Sum(matrix, x, y - 1, path + "0", sum, seq); //jest to tak jakby drzewo ktore sprawdzi wszystkie kombinacje bez potrzeby petli

        }
    }
}