Question

C++ CODE ONLY

Using the following code.

#include <iostream>
#include <string>
#include <climits>
#include <algorithm>
using namespace std;

// M x N matrix
#define M 5
#define N 5

// Naive recursive function to find the minimum cost to reach
// cell (m, n) from cell (0, 0)
int findMinCost(int cost[M][N], int m, int n)
{
   // base case
   if (n == 0 || m == 0)
       return INT_MAX;

   // if we're at first cell (0, 0)
   if (m == 1 && n == 1)
       return cost[0][0];

   // include cost of the current cell in path and recur to find minimum
   // of the path from adjacent left cell and adjacent top cell.
   return min (findMinCost(cost, m - 1, n), findMinCost(cost, m, n - 1))
               + cost[m - 1][n - 1];
}

int main()
{
   int cost[M][N] =
   {
       { 4, 7, 8, 6, 4 },
       { 6, 7, 3, 9, 2 },
       { 3, 8, 1, 2, 4 },
       { 7, 1, 7, 3, 7 },
       { 2, 9, 8, 9, 3 }
   };

   cout << "The minimum cost is " << findMinCost(cost, M, N);

   return 0;
}

Answer the following questions:

Given a M x N matrix where each cell has a cost associated with it, find the minimum cost to reach last cell (0,0) of the matrix from its first cell (M,N). We can only move one unit right or one unit down from any cell. i.e. from cell (I,j), we can move to (i, j-1) or (i-1,j).

1. Suppose that are also allowed to move diagonally to lower-right cell as well as downward and right. Find the minimum cost using pure recursion. (30 points)

Example output:

Minimum cost is 34.

Answer 1

#include <bits/stdc++.h>

using namespace std;

#define ROW 5

#define COL 5

struct cell

{

    int x, y;

    int distance;

    cell(int x, int y, int distance) :

        x(x), y(y), distance(distance) {}

};

bool operator<(const cell& a, const cell& b)

{

    if (a.distance == b.distance)

    {

        if (a.x != b.x)

            return (a.x < b.x);

        else

            return (a.y < b.y);

    }

    return (a.distance < b.distance);

bool isInsideGrid(int i, int j)

{

    return (i >= 0 && i < COL && j >= 0 && j < ROW);

}

int shortest(int grid[ROW][COL], int row, int col)

{

    int dis[row][col];

  

    for (int i = 0; i < row; i++)

        for (int j = 0; j < col; j++)

            dis[i][j] = INT_MAX;

     int dx[] = {-1, 0, 1, 0};

    int dy[] = {0, 1, 0, -1};

    set<cell> st;

  

    st.insert(cell(0, 0, 0));

    dis[0][0] = grid[0][0];

  

    while (!st.empty())

    {

  

        cell k = *st.begin();

        st.erase(st.begin());

        for (int i = 0; i < 4; i++)

        {

            int x = k.x + dx[i];

            int y = k.y + dy[i];

  

            if (!isInsideGrid(x, y))

                continue;

            if (dis[x][y] > dis[k.x][k.y] + grid[x][y])

            {

              

                if (dis[x][y] != INT_MAX)

                    st.erase(st.find(cell(x, y, dis[x][y])));

                dis[x][y] = dis[k.x][k.y] + grid[x][y];

                st.insert(cell(x, y, dis[x][y]));

            }

        }

    }

    for (int i = 0; i < row; i++, cout << endl)

        for (int j = 0; j < col; j++)

            cout << dis[i][j] << " ";

    

    return dis[row - 1][col - 1];

}

int main()

{

    int grid[ROW][COL] =

    {

        31, 100, 65, 12, 18,

        10, 13, 47, 157, 6,

        100, 113, 174, 11, 33,

        88, 124, 41, 20, 140,

        99, 32, 111, 41, 20

    };

    cout << shortest(grid, ROW, COL) << endl;

    return 0;

}