Find the least distance in a matrix C++

Question

So I want to make a recursive C++ program to find the minimum distance a person should go from top to bottom of a matrix. The person can go downward, diagonal right, and diagonal left. I need to display the total distance and which number he went through. This code works if I'm trying to find the maximum distance, but got an error when i turn it into finding the minimum distance. Any idea? Ps: I must use recursive function, no loops Thanks!

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

I think that you wanted to check "downward" `col_now` without `col_now > 0` guard and "diagonal left" `col_now - 1` with that guard. — luantkow, Sep 27 '20 at 12:55
This reads like it's from some contest/challenge/competitive coding/hacking site. Is it? If your goal is to learn C++, you won't learn anything there. In nearly all cases, like this one, the correct solution is based on a mathematical or a programming trick. If you don't know what the trick is and attempt to code a brute-force approach, the program runs slow and fails for that reason. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Sam Varshavchik, Sep 27 '20 at 13:17

score 0 · Accepted Answer · answered Sep 27 '20 at 13:41

I've spotted two errors in your code, the first one is that you evaluating the diagonal left step without checking if such step can be made:

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

And then you are evaluating the downward step only if diagonal left step can be made:

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

The second issue is in Start function:

if (start == end)
    return 0;

The recursion exit condition returns 0 which most probably trumps valid paths. You have to:

Return the value so big that it won't be used by calling Start function:
```
 if (start == end)
     return std::numeric_limits<int>::max();
```

Rewrite the Start function to not call the function at all when exit condition will be met:

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

Also:

Don't use names like temp in code that you want to share with anybody. It will help you to understand code better and hopefully spot your mistakes.

Test your code:

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

Find the least distance in a matrix C++

1 Answers1