this is the complete part function which is related to the above first part of the code.
Code:
void spmtn1(int r, int c) {
sq[r][c] = ' '; /* Mark the square we have visited so that it won't be visited again */
/* Upon the destination point is found, check the current value of ctr1 with the value in *
* the array, if the current value of ctr1 is less, update it and display message */
if (r == dRow && c == dCol) {
if (ctr1 < spmtn[m]) {
spmtn[m] = ctr1;
printf("Shortest monotone path: %d\n", spmtn[m]);
return;
}
}
else
ctr1++;
/* To compute the minimal monotone paths from the origin point to destination point *
* Either the point before the origin point or before the turning point has not been visited, *
* only the origin point or turning point has been visited, so the next point it moving to can be *
* less than or greater than or equal to the origin or turning point *
* If the previous two points have been visited, then check if the previous point is greater than or equal *
* to the one before then the next point it moving to must be greater than or equal to the previous point, *
* so does less than or equal to. If not then the line will turn vertically or horizontally to next direction */
if (c > dCol && sq[r][c - 1] != '#' && sq[r][c - 1] != ' ') {
if (sq[r][c] == ' ' && sq[r][c + 1] != ' ') {
spmtn1(r, c - 1);
}
}
if (c > dCol && sq[r][c - 1] != '#' && sq[r][c - 1] != ' ') {
if (sq[r][c] == ' ' && sq[r][c + 1] == ' ') {
if ((sq[r][c] >= sq[r][c + 1] && sq[r][c - 1] >= sq[r][c]) || (sq[r][c] <= sq[r][c + 1] && sq[r][c - 1] <= sq[r][c])) {
spmtn1(r, c - 1);
}
}
}
else
if (c < dCol && sq[r][c + 1] != '#' && sq[r][c + 1] != ' ') {
if (sq[r][c] == ' ' && sq[r][c - 1] != ' ') {
spmtn1(r, c + 1);
}
}
if (c < dCol && sq[r][c + 1] != '#' && sq[r][c + 1] != ' ') {
if (sq[r][c] == ' ' && sq[r][c - 1] == ' ') {
if ((sq[r][c] >= sq[r][c - 1] && sq[r][c + 1] >= sq[r][c]) || (sq[r][c] <= sq[r][c - 1] && sq[r][c + 1] <= sq[r][c])) {
spmtn1(r, c + 1);
}
}
}
else
if (r > dRow && sq[r - 1][c] != '#' && sq[r - 1][c] != ' ') {
if (sq[r][c] == ' ' && sq[r + 1][c] != ' ') {
spmtn1(r - 1, c);
}
}
if (r > dRow && sq[r - 1][c] != '#' && sq[r - 1][c] != ' ') {
if (sq[r][c] == ' ' && sq[r + 1][c] == ' ') {
if ((sq[r][c] >= sq[r + 1][c] && sq[r - 1][c] >= sq[r][c]) || (sq[r][c] <= sq[r + 1][c] && sq[r - 1][c] <= sq[r][c])) {
spmtn1(r - 1, c);
}
}
}
else
if (r < dRow && sq[r + 1][c] != '#' && sq[r + 1][c] != ' ') {
if (sq[r][c] == ' ' && sq[r - 1][c] != ' ') {
spmtn1(r + 1, c);
}
}
if (r < dRow && sq[r + 1][c] != '#' && sq[r + 1][c] != ' ') {
if (sq[r][c] == ' ' && sq[r - 1][c] == ' ') {
if ((sq[r][c] >= sq[r - 1][c] && sq[r + 1][c] >= sq[r][c]) || (sq[r][c] <= sq[r - 1][c] && sq[r + 1][c] <= sq[r][c])) {
spmtn1(r + 1, c);
}
}
}
else {
/* If has been stopped by '#' or marked square that has been visited, so move in any direction we can */
if (r + 1 < row && sq[r + 1][c] != '#' && sq[r + 1][c] != ' ')
spmtn1(r + 1, c);
else
if (r - 1 > 0 && sq[r - 1][c] != '#' && sq[r - 1][c] != ' ')
spmtn1(r - 1, c);
else
if (c + 1 < col && sq[r][c + 1] != '#' && sq[r][c + 1] != ' ')
spmtn1(r, c + 1);
else
if (c - 1 > 0 && sq[r][c - 1] != '#' && sq[r][c - 1] != ' ')
spmtn1(r, c - 1);
}
/* No monotone path exists */
if (r + 1 < row && sq[r + 1][c] != '#' && sq[r + 1][c] != ' ')
spmtn1(r + 1, c);
else
if (r - 1 > 0 && sq[r - 1][c] != '#' && sq[r - 1][c] != ' ')
spmtn1(r - 1, c);
else
if (c + 1 < col && sq[r][c + 1] != '#' && sq[r][c + 1] != ' ')
spmtn1(r, c + 1);
else
if (c - 1 > 0 && sq[r][c - 1] != '#' && sq[r][c - 1] != ' ')
spmtn1(r, c - 1);
else
printf("No monotone path exists\n");
} And this is the complete part function which is related to the above second part of the code.
Code:
void spmw1(int r, int c) {
sq[r][c] = ' '; /* Mark the square we have visited so that it won't be visited again */
/* Upon the destination point is found, check the current value of ctr2 with the value in *
* the array, if the current value of ctr2 is less, update it and display message together *
* with the minimal weights information */
if (r == dRow && c == dCol) {
if (ctr2 < spmw[n]) {
spmw[n] = ctr2;
printf("Shortest path of minimal weight: %d -- weight %d\n", spmw[n], mw);
return;
}
}
else {
mw += sq[r][c];
ctr2++;
vpath[ctr2][0] = r;
vpath[ctr2][1] = c;
}
/* To compute the minimal paths of minimal weights from the origin point to destination point *
* First check the four surrounding points of origin point, up, down, left and right to ensure *
* one or more point is not equal to '#' and marked square *
* if (c < dCol) statement is evaluated to true, the next priority moving point to will be (r, c + 1) *
* provided that it is not equal to '#', marked square and has the least or equal value among the *
* surrounding points, otherwise it will move to different direction either horizontally or vertically. *
* So do other if statements. */
if (c > dCol && sq[r][c - 1] != '#' && sq[r][c - 1] != ' ' || sq[r + 1][c] != '#' && sq[r + 1][c] != ' ' ||
sq[r][c + 1] != '#' && sq[r][c + 1] != ' ' || sq[r - 1][c] != '#' && sq[r - 1][c] != ' ' &&
sq[r][c - 1] <= sq[r + 1][c] && sq[r][c - 1] <= sq[r][c + 1] && sq[r][c - 1] <= sq[r - 1][c])
spmw1(r, c - 1);
else
if (c < dCol && sq[r][c + 1] != '#' && sq[r][c + 1] != ' ' || sq[r - 1][c] != '#' && sq[r - 1][c] != ' ' ||
sq[r][c - 1] != '#' && sq[r][c - 1] != ' ' || sq[r + 1][c] != '#' && sq[r + 1][c] != ' ' &&
sq[r][c + 1] <= sq[r - 1][c] && sq[r][c + 1] <= sq[r][c - 1] && sq[r][c + 1] <= sq[r + 1][c])
spmw1(r, c + 1);
else
if (r > dRow && sq[r - 1][c] != '#' && sq[r - 1][c] != ' ' || sq[r][c - 1] != '#' && sq[r][c - 1] != ' ' ||
sq[r + 1][c] != '#' && sq[r + 1][c] != ' ' || sq[r][c + 1] != '#' && sq[r][c + 1] != ' ' &&
sq[r - 1][c] <= sq[r][c - 1] && sq[r - 1][c] <= sq[r + 1][c] && sq[r - 1][c] <= sq[r][c + 1])
spmw1(r - 1, c);
else
if (r < dRow && sq[r + 1][c] != '#' && sq[r + 1][c] != ' ' || sq[r][c + 1] != '#' && sq[r][c + 1] != ' ' ||
sq[r - 1][c] != '#' && sq[r - 1][c] != ' ' || sq[r][c - 1] != '#' && sq[r][c - 1] != ' ' &&
sq[r + 1][c] <= sq[r][c + 1] && sq[r + 1][c] <= sq[r - 1][c] && sq[r + 1][c] <= sq[r][c - 1])
spmw1(r + 1, c);
else {
/* If has been stopped by '#' or marked square that has been visited, so move in any direction we can */
if (r + 1 < row && sq[r + 1][c] != '#' && sq[r + 1][c] != ' ')
spmw1(r + 1, c);
else
if (r - 1 > 0 && sq[r - 1][c] != '#' && sq[r - 1][c] != ' ')
spmw1(r - 1, c);
else
if (c + 1 < col && sq[r][c + 1] != '#' && sq[r][c + 1] != ' ')
spmw1(r, c + 1);
else
if (c - 1 > 0 && sq[r][c - 1] != '#' && sq[r][c - 1] != ' ')
spmw1(r, c - 1);
}
/* When you reach a point will not be able to move anywhere else, this will cause the *
* backtracking to execute */
if (r + 1 < row && sq[r + 1][c] != '#' && sq[r + 1][c] != ' ')
spmw1(r + 1, c);
else
if (r - 1 > 0 && sq[r - 1][c] != '#' && sq[r - 1][c] != ' ')
spmw1(r - 1, c);
else
if (c + 1 < col && sq[r][c + 1] != '#' && sq[r][c + 1] != ' ')
spmw1(r, c + 1);
else
if (c - 1 > 0 && sq[r][c - 1] != '#' && sq[r][c - 1] != ' ')
spmw1(r, c - 1);
else {
ctr2--;
if (ctr2 <= 0)
printf("No path exists\n");
else
spmw1(vpath[ctr2][0], vpath[ctr2][1]);
}
}