Mountain Travelers - Githubissues

Write a function to simulate two travelers moving in a mountain.

Task Description

We have an N by M map of the mountain. The vertical index is from 0 to N - 1, and the horizontal index is from 0 to M - 1. An integer in a cell indicates the height of the mountain, and we assume that all cells have different heights. Every cell has up to eight neighbors. The coordinate system is defined as follows:

figure

There are two travelers - one always goes uphill into the steepest neighbor, and the other always goes downhill into the steepest neighbor. The travelers will stop if any of the following conditions happens.

They go into the same cell.
They cannot find a uphill/downhill neighbor.
They go into cell that has been visited by the other traveler.

We want to record the paths of the travelers with a sequence of integers from 0 to 7, as in the following list. Note that a -1 at the end indicates that the traveler has stopped.

Let the current position (row, column) of a traveler be (r, c).

If the traveler moves from (r, c) to (r, c+1), the direction is 0.
If the traveler moves from (r, c) to (r, c-1), the direction is 1.
If the traveler moves from (r, c) to (r+1, c), the direction is 2.
If the traveler moves from (r, c) to (r-1, c), the direction is 3.
If the traveler moves from (r, c) to (r+1, c+1), the direction is 4.
If the traveler moves from (r, c) to (r-1, c-1), the direction is 5.
If the traveler moves from (r, c) to (r-1, c+1), the direction is 6.
If the traveler moves from (r, c) to (r+1, c-1), the direction is 7.

Write a function to simulate two traveler movement on the map, and store the directions of the movement of the uphill traveler into array directionA, and the directions of the downhill traveler into array directionB. The function prototype in travel.h is as follows:

void travel(int map[1024][1024], int N, int M, int A_r, int A_c, int B_r, int B_c, int directionA[], int directionB[]);

Note

You only need to submit the function travel. No main program is necessary because TA will write it to test your function. The judge program will call your travel() function and pass the seven parameters, then read the result through two array, so it is not necessary to read input data or output any messages in the travel() function.

A main program that will print out the codes after calling travel is as follow:

#include <stdio.h>
#include "travel.h"

int main() {
    int N, M;
    int map[1024][1024];
    int A_r, A_c, B_r, B_c;
    int directionA[1024], directionB[1024];

    scanf("%d%d", &N, &M);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &map[i][j]);
        }
    }

    scanf("%d%d%d%d", &A_r, &A_c, &B_r, &B_c);

    travel(map, N, M, A_r, A_c, B_r, B_c, directionA, directionB);

    int i = 0;
    while (directionA[i] != -1) {
        printf("%d ", directionA[i]);
        i++;
    }
    printf("-1\n");
    i = 0;
    while (directionB[i] != -1) {
        printf("%d ", directionB[i]);
        i++;
    }
    printf("-1\n");

    return 0;
}

Subtask

30 points: Two travelers will NOT meet each other during the travel.
70 points: Two travelers might meet each other during the travel.

Input format used by the main program attached

The first line has N and M, which are the vertical and horizontal size of the map. The next R lines has the map represents the mountain. The second to the the line has A_r, A_c, which are the initial row, column index of the traveler who goes uphill. The last line has B_r and B_c, which are the initial row, column index of the traveler who goes downhill. It is guarantee that the number of steps for each traveler will not exceed 1023.

Output format of the main program attached

In the main program, we will print the content of array directionA and array directionB.

Sample Input 1

5 5
50 45 40 35 75
55 99 42 85 25
2  41 96 6  20
65 40 5  3  15
70 30 1  4  10
4 3
0 4

Sample Output 1

6 3 5 7 5 -1
2 7 2 7 -1

Sample Input 2

5 5
50 49 40 35 1
54 99 47 55 32
77 86 60 33 31
73 70 64 68 84
80 85 66 7  2
0 4
4 0

Sample Output 2

7 7 -1
6 6 -1

Sample Input 3

6 6
14 15 16 86 94 99
12 13 75 83 89 93
11 10 76 79 82 88
9  52 69 77 78 5
53 59 54 2  4  6
49 52 1  3  7  8
5 0
0 5

Sample Output 3

6 6 6 -1
7 7 7 -1

Sample Input 4

5 5
76 94 99 98 1
72 75 73 64 0
63 74 66 55 44
61 69  3  2 33
59 62 22 11 5
3 3
1 1

Sample Output 4

5 5 -1
7 2 2 -1

pangfengliu / programmingtasks

Mountain Travelers #342