c++ - 在矩阵 C++ 中找到最小距离

问题描述

所以我想制作一个递归 C++ 程序来找到一个人应该从矩阵的顶部到底部的最小距离。该人可以向下、向右和向左倾斜。我需要显示总距离和他经过的数字。如果我试图找到最大距离，则此代码有效，但是当我将其转换为找到最小距离时出现错误。任何的想法？Ps：我必须使用递归函数，没有循环谢谢！

   int SearchPath(int row_now, int col_now, int** arr, int row, int col, int total) {
    if (row_now == row - 1) {
        return total + arr[row_now][col_now];
    }
    int min = SearchPath(row_now + 1, col_now - 1, arr, row, col, total + arr[row_now][col_now]);
    if (col_now > 0) {
        int temp = SearchPath(row_now + 1, col_now, arr, row, col, total + arr[row_now][col_now]);
        if (temp<min)
            min = temp;
    }
    if (col_now < col - 1) {
        int temp = SearchPath(row_now + 1, col_now + 1, arr, row, col, total + arr[row_now][col_now]);
        if (temp<min)
            min = temp;
    }
    return min;
}

int Start(int start, int end, int** arr, int row, int col) {
    if (start == end)
        return 0;

    int min = SearchPath(0, start, arr, row, col, 0);
    int temp = Start(start + 1, end, arr, row, col);

    if (temp < min)
        return temp;
    else
        return min;
}

标签： c++recursion

我在您的代码中发现了两个错误，第一个是您在评估左对角线步骤时没有检查是否可以进行这样的步骤：

int min = SearchPath(row_now + 1, col_now - 1, arr, row, col, total + arr[row_now][col_now]);

然后，仅当可以进行对角左步时，您才评估向下的步：

if (col_now > 0) {
    int temp = SearchPath(row_now + 1, col_now, arr, row, col, total + arr[row_now][col_now]);
    if (temp<min)
        min = temp;
}

第二个问题是在 Start 函数中：

if (start == end)
    return 0;

递归退出条件返回 0，这很可能胜过有效路径。你必须：

返回值太大以至于调用 Start 函数不会使用它：

 if (start == end)
     return std::numeric_limits<int>::max();

重写 Start 函数以在满足退出条件时根本不调用该函数：

 int Start(int start, int end, int** arr, int row, int col) {
     const int current_column_result = SearchPath(0, start, arr, row, col, 0);
     const int next_column = start + 1;

     if(end != next_column)
     {
         int next_column_result = Start(next_column, end, arr, row, col);

         if (next_column_result < current_column_result)
             return next_column_result;
     }
     return current_column_result;
 }

还：

不要使用temp您想与任何人共享的代码中的名称。它将帮助您更好地理解代码并希望发现您的错误。

测试你的代码：

  struct TwoDimmensionArray
  {
      TwoDimmensionArray(std::initializer_list<std::initializer_list<int>> rows)
      {
           buff.reserve(rows.size());
           array = std::make_unique<int*[]>(rows.size());
           int** current_row = array.get();

           for(const auto& row : rows)
           {
               auto new_row = std::make_unique<int[]>(row.size());

               std::copy(std::begin(row), std::end(row), new_row.get());

               *(current_row++) = new_row.get();

               buff.push_back(std::move(new_row));
           }
       }

       operator int**() const
       {
           return array.get();
       }

       std::vector<std::unique_ptr<int[]>> buff;
       std::unique_ptr<int*[]> array;
   };

   int Start(int** arr, int row, int col)
   {
       return Start(0, col, arr, row, col);
   }

   void test_one_element()
   {
       assert(Start(TwoDimmensionArray{{1}}, 1, 1) == 1);
   }

   void test_three_elements()
   {
       assert(Start(TwoDimmensionArray{ {3,1,3},
                                        {3,2,1},
                                        {3,2,3} }, 3, 3) == 4);
   }

   int main()
   {
       test_one_element();
       test_three_elements();

       return 0;
   }

c++ - 在矩阵 C++ 中找到最小距离

问题描述

解决方案

推荐阅读