Поиск кратчайшего пути в матрице - C#

Узнай цену своей работы

Формулировка задачи:

Привет всем, есть задание: "Считать из файла input3.txt двумерный массив. Каждая ячейка имеет вес указанный в матрице, необходимо найти кратчайший маршрут из правого верхнего в левый нижний. Результат записать в файл output3.txt." Ребята, мозг себе выел, может кто-нибудь подсказать, описать алгоритм нахождения пути? Препод говорит что как-то через рекурсию можно сделать. Буду очень благодарен если кто-нибудь отпишет. И да, как бы "ходить" можно только вниз и вверх.
Тьфу влево и вниз.

Решение задачи: «Поиск кратчайшего пути в матрице»

textual
Листинг программы
 static void Main(string[] args)
        {
            const int  size =   4;
            int index = 0;
            List<int> list = new List<int>();
            Random random = new Random();
            int[,] arr2 = new int[size, size];
            
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j <size; j++)
                {
                    arr2[i, j] = random.Next(1, 10);
 
                    Console.Write(" " + arr2[i, j]);
                }
                Console.WriteLine();
            }
 
            Console.WriteLine();
            Rekursiya(arr2, size, size, list);
           // минимальное число, и значение его  jго индекса
            foreach (var VARIABLE in list)
            {
                for (int i = list.Count-1; i >0; i--)
                {
                    if (list[i] < VARIABLE)
                    {
                        index = i;
                    }
                }
            }
 
            Console.WriteLine("Кратчайший путь ");
 
            for (int i = 0; i < size; i++)
            {
                for (int j = (list.Count - 1 - index); j == list.Count - 1 - index; j--)
                {
                    Console.WriteLine(arr2[i,j] + " " + i + "," + j);
                }
            }
            Console.ReadLine();
        }
// Собственно сама рекурсия.
           static void  Rekursiya(int[,] arr,int x,int y, List<int> list )
        {
            int temp ;      
          
                temp = 0;
 
                for (int i = 0; i < y; i++)
                {
                    for (int j = x - 1; j >= 0; j--)
                    {
                        temp += arr[i, j];
 
                        break;
                    }                
                }
                if (list.Count < y)
                {
                    list.Add(temp);
                }
 
            if (x > 1)
            {
                x--;
                Rekursiya(arr, x, y, list);
            }
        }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

6   голосов , оценка 4 из 5