The Problem You must write a program that will compute the minimum cost path thr

Question

The Problem You must write a program that will compute the minimum cost path through a matrix of integers. For this assignment, you must make use of recursion for all of your repetition. i.e.you may not use any for, while, or do-while loops in your program. Background A matrix of integers is represented in a computer as a 2-D array of integers. The path will start in column 0 (the first column) and consists of a sequence of steps terminating in column x (the last column). A step consists of traveling from columni to column i+1 in an adjacent (horizontal or diagonal) row. Legal steps are illustrated below The cost of a path is the sum of the integers in each of the n cells of the matrix that are visited For example in the matrix shown below the path with minimum cost is 15 and is show: 4 1 2 8 6 6N814 312|1|3

Explanation / Answer

here is your program : ---------->>>>>>>>

#include<iostream>
#include<fstream>
#define MAX 100

using namespace std;

void takeInput(int arr[MAX][MAX],int i,int j,int col,int row,ifstream &ifs){
if(j == col){
  j = 0;
  i++;
}
if(i == row){
  return;
}
ifs>>arr[i][j];
takeInput(arr,i,j+1,col,row,ifs);
}

int find_minimal_cost(int arr[MAX][MAX],int row,int col,int i,int j){
int cost = arr[i][j];
int cost1 = MAX*10,cost2 = MAX*10,cost3 = MAX*10;
if(j >= col){
  return 0;
}
if(i - 1 >= 0){
  cost1 = find_minimal_cost(arr,row,col,i-1,j+1);
}
cost2 = find_minimal_cost(arr,row,col,i,j+1);
if(i+1 < row){
  cost3 = find_minimal_cost(arr,row,col,i+1,j+1);
}

if(cost1 <= cost2 && cost1 <= cost3){
  cost1 = cost1 + cost;
  return cost1;
}else if(cost2 <= cost1 && cost2 <= cost3){
  cost2 = cost2 + cost;
  return cost2;
}else if(cost3 <= cost1 && cost3 <= cost2){
  cost3 = cost3 + cost;
  return cost3;
}
}

void find_minimal_path(int arr[MAX][MAX],int row,int col,int i,int j){
int cost1 = MAX*10,cost2 = MAX*10,cost3 = MAX*10;
if(j > col){
  return;
}
if(i - 1 >= 0){
  cost1 = find_minimal_cost(arr,row,col,i-1,j+1);
}
cost2 = find_minimal_cost(arr,row,col,i,j+1);
if(i+1 < row){
  cost3 = find_minimal_cost(arr,row,col,i+1,j+1);
}

if(cost1 <= cost2 && cost1 <= cost3){
  cost1 = cost1 + arr[i][j];
  if(j == 0){
   cout<<cost1<<endl;
  }
  cout<<"("<<i<<", "<<j<<")";
  find_minimal_path(arr,row,col,i-1,j+1);
}else if(cost2 <= cost1 && cost2 <= cost3){
  cost2 = cost2 + arr[i][j];
  if(j == 0){
   cout<<cost2<<endl;
  }
  cout<<"("<<i<<", "<<j<<")";
  find_minimal_path(arr,row,col,i,j+1);
}else if(cost3 <= cost1 && cost3 <= cost2){
  cost3 = cost3 + arr[i][j];
  if(j == 0){
   cout<<cost3<<endl;
  }
  cout<<"("<<i<<", "<<j<<")";
  find_minimal_path(arr,row,col,i+1,j+1);
}
}

int main(){
ifstream ifs;
string filename;
int arr[MAX][MAX];
int row,col;
cout<<" Enter the Input Filename : ";
cin>>filename;
ifs.open(filename.c_str());
if(!ifs.is_open()){
  cout<<" File Openining error check input file";
  return 0;
}
ifs>>row>>col;
takeInput(arr,0,0,col,row,ifs);
find_minimal_path(arr,row,col,0,0);
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.