D2L Bright space Problem F Muddy Hike Liam is planning out his route for an upco

Question

D2L Bright space Problem F Muddy Hike Liam is planning out his route for an upcoming nature hike. Unfortunately, the region that he plans on hiking through is notoriously muddy, so in order to prevent his floral shirt from getting covered with mud, he has decided to pick a route for which the maximum depth of mud encountered is minimized. The terrain is modelled as a two-dimensional grid, with nonnegative integers giving the depth of the mud in each cell in micrometers (millionths of a meter). The hike must begin at one of the cells in the leftmost column of the grid and finish at one of the cells in the rightmost column of the grid. Image by Kerstin Herrmann (Pixabay, PublicDomain Liam is allowed to move either north, south, east, or west, but he cannot travel diagonally. astmis Problem ID maps17.mu CPU Time limit 4 secon Memory limit: 1024 MB Download Sample data files

Explanation / Answer

#include<stdio.h>
#include<limits.h>

typedef struct data {
   long weight;
   long max;
}Data;
int row,col;
Data findPath(int **matrix, int presentRow, int presentCol, Data wt) {
   int **copy(int**), **cpy;
   Data temp ;
   temp.weight = wt.weight;
   temp.max = wt.max;
  
   Data minData(Data, Data, Data, Data);
   Data a, b, c, d;
   if (presentCol==col)
       return temp; //reached final destination
   if (presentRow < 0 || presentRow >= row || presentCol < 0) {
       temp.weight = temp.max = LONG_MAX; //mark invalid
       return temp;
   }
   if (matrix[presentRow][presentCol] <= 0) {
       temp.weight =   temp.max = LONG_MAX; //mark invalid
       return temp;
   }
   temp.weight += matrix[presentRow][presentCol]; //update weight
   if (matrix[presentRow][presentCol] > temp.max)
       temp.max = matrix[presentRow][presentCol]; //update max depth
   cpy = copy(matrix); //copy the matrix
   cpy[presentRow][presentCol] = -4;//mark preset location invalid
  
   a = findPath(cpy, presentRow, presentCol + 1, temp); //dynamic algo to four ways
   b = findPath(cpy, presentRow + 1, presentCol, temp);
   c = findPath(cpy, presentRow, presentCol - 1, temp);
   d = findPath(cpy, presentRow - 1, presentCol, temp);
   return minData(a,b,c,d); // get minimum
}

int **copy(int **a) {
   int i,j;
   int **b = malloc(sizeof(int*)*row);
   for (i=0; i<row; i++) {
       b[i] = malloc(sizeof(int)*col);
       for (j=0; j<col; j++)
           b[i][j] = a[i][j];
   }
   return b;
}

Data minData(Data a, Data b, Data c, Data d) {
   Data temp;
   temp.weight = a.weight;
   temp.max = a.max;
   if (temp.weight > b.weight){
       temp.weight = b.weight;
   temp.max = b.max;
   }
   if (temp.weight > c.weight){
       temp.weight = c.weight;
   temp.max = c.max;
   }
   if (temp.weight > d.weight){
       temp.weight = d.weight;
   temp.max = d.max;
   }
  
   return temp;
}

int **init(FILE *FP) {
   int i, j, **b;
   fscanf(FP, "%d",&row);
   fscanf(FP, "%d",&col);
   b = malloc(sizeof(int*)*row);
   for (i=0; i<row; i++) {
       b[i] = malloc(sizeof(int)*col);
       for (j=0; j<col; j++)
           fscanf(FP,"%d",&b[i][j]);
   }
  
   return b;
}

void main() {
   FILE *FP = fopen("data.txt","r");
   int **adj = init(FP), i,j;
   Data min, temp, deflt, a, b, c, d;
   deflt.weight = 0;
   deflt.max = 0;
   min = findPath(adj, 0, 0, deflt);
  
   for (i=1; i<row; i++) { //to simulate starting from every row
       temp = findPath(adj, 1, 0, deflt);
       if (temp.weight < min.weight)
           min = temp;
   }

   printf("%ld",min.max);
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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