Question

A rat is in a square maze of dimension N (1-index based). Maze contains 3 types of cells namely: holes (H), pipes (P) and special (S). If the current cell is of type holes, then rat can move to the other adjacent cell which is of type holes only. Same holds true for cells of type pipes and special. Besides this, special cell also has one more property i.e. if the current cell is of type special, then rat can also move to other adjacent cells of type holes and pipes. Simply put, a special cell can connect two cells of type holes and pipes. In the maze every cell contains a cheese of weight Wij and some cells are marked as walls (W). In case, if adjacent cell is of type wall then rat can't move to the adjacent cell.

The rat will start at (1, 1) and it has to reach cell (N, N), it is allowed to move only down or right, and it has to eat the maximum of the available cheese. Your task is to find out the maximum cheese that rat can eat in the journey from (1, 1) to (N, N). In case, if rat can't able to reach (N,

Answer 1

#include <stdio.h>#include <string.h> int main() {    int n; // size of board    int i, j, k, l; // counters    char type[10][10][100];    float weight[10][10];    float totalWeight[10][10];     // Input    printf("Enter the size ofboard: ");    scanf("%d", &n);    for (i = 1; i <= n; i++) {        for (j = 1; j <= n; j++) {           printf("Enter the type of cell (%d, %d) (H, P, S, W): ", i, j);           scanf("%s", type[i][j]);            totalWeight[i][j] = -1;        }    }     for (i = 1; i <= n; i++) {        for (j = 1; j <= n; j++) {           printf("Enter the weight of cheese in cell (%d, %d): ", i, j);           scanf("%f", &weight[i][j]);        }    }     // Dijkstra typealgorithm    if (strcmp(type[1][1], "W") != 0) {       totalWeight[1][1] = weight[1][1];        for (k = 2; k < 2 * n; k++) {           if (k <= n + 1) {               l = 1;           } else {               l = k - n;           }           for (i = l; i <= k - l; i++) {               j = k - i;               if (totalWeight[i][j] > 0) {                    if ((i + 1 <= n) && (strcmp(type[i + 1][j], "W") != 0)) {                        if ((strcmp(type[i][j], type[i + 1][j]) == 0) || (strcmp(type[i][j], "S") == 0) || (strcmp(type[i + 1][j], "S") == 0)) {                            if (weight[i + 1][j] + totalWeight[i][j] > totalWeight[i + 1][j]) {                                totalWeight[i + 1][j] = totalWeight[i][j] + weight[i + 1][j];                            }                        }                    }                    if ((j + 1 <= n) && (strcmp(type[i][j + 1], "W") != 0)) {                        if ((strcmp(type[i][j], type[i][j + 1]) == 0) || (strcmp(type[i][j], "S") == 0) || (strcmp(type[i][j + 1], "S") == 0)) {                            if (weight[i][j + 1] + totalWeight[i][j] > totalWeight[i][j + 1]) {                                totalWeight[i][j + 1] = totalWeight[i][j] + weight[i][j + 1];                            }                        }                    }               }           }        }        if (totalWeight[n][n] > 0) {           printf("Maximal weight of cheese %f", totalWeight[n][n]);        } else {           printf("It is impossible to reach bottom right cell!");        }    } else {       printf("It is impossible to reach bottom right cell!");    }     return 0;}