# 50088. Mountain Travelers

## I'm a slow walker, but I never walk backwards.

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

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:

1void 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:

123456789101112131415161718192021222324252627282930313233343536#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;}


• 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 550 45 40 35 7555 99 42 85 252  41 96 6  2065 40 5  3  1570 30 1  4  104 30 4


## Sample Output 1

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


## Sample Input 2

5 550 49 40 35 154 99 47 55 3277 86 60 33 3173 70 64 68 8480 85 66 7  20 44 0


## Sample Output 2

7 7 -16 6 -1


## Sample Input 3

6 614 15 16 86 94 9912 13 75 83 89 9311 10 76 79 82 889  52 69 77 78 553 59 54 2  4  649 52 1  3  7  85 00 5


## Sample Output 3

6 6 6 -17 7 7 -1


## Sample Input 4

5 576 94 99 98 172 75 73 64 063 74 66 55 4461 69  3  2 3359 62 22 11 53 31 1


## Sample Output 4

5 5 -17 2 2 -1