Answer to Question #44996 in C for Palak

Question #44996
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,
1
Expert's answer
2014-08-21T03:27:56-0400
#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;
}

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS