50088. Mountain Travelers
難度：4.7/5 Used Time: 28:54
邊界條件非常多，必重練。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75#include <stdio.h>
#include <limits.h>
#include "travel.h"
int vis[1024][1024] = {0};
int dx[8] = {0, 0, 1, -1, 1, -1, -1, 1};
int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
static inline int is_valid(int x, int y, int n, int m){
return x >= 0 && y >= 0 && x < n && y < m;
}
int find_max_idx(int map[1024][1024], int x, int y, int n, int m){
int max_idx = -1, max_num = INT_MIN;
for(int d = 0; d < 8; d++){
int now_x = x + dx[d], now_y = y + dy[d];
if(!is_valid(now_x, now_y, n, m)) continue;
if(map[now_x][now_y] > max_num){
max_idx = d;
max_num = map[now_x][now_y];
}
}
if(max_num < map[x][y]) return -1;
else return max_idx;
}
int find_min_idx(int map[1024][1024], int x, int y, int n, int m){
int min_idx = -1, min_num = INT_MAX;
for(int d = 0; d < 8; d++){
int now_x = x + dx[d], now_y = y + dy[d];
if(!is_valid(now_x, now_y, n, m)) continue;
if(map[now_x][now_y] < min_num){
min_idx = d;
min_num = map[now_x][now_y];
}
}
if(min_num > map[x][y]) return -1;
else return min_idx;
}
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[]){
vis[a_r][a_c] = 1, vis[b_r][b_c] = 1;
int ptr_a = 0, ptr_b = 0;
int a_mov = 1, b_mov = 1;
int rtv_a, rtv_b;
while(a_mov || b_mov){
if(a_mov) rtv_a = find_max_idx(map, a_r, a_c, n, m);
if(b_mov) rtv_b = find_min_idx(map, b_r, b_c, n, m);
if(a_mov) directionA[ptr_a++] = rtv_a;
if(b_mov) directionB[ptr_b++] = rtv_b;
if(rtv_a == -1) a_mov = 0;
if(rtv_b == -1) b_mov = 0;
if(a_mov) a_r += dx[rtv_a], a_c += dy[rtv_a];
if(b_mov) b_r += dx[rtv_b], b_c += dy[rtv_b];
if(a_mov && vis[a_r][a_c] == 1){
directionA[ptr_a++] = -1;
a_mov = 0;
}
if(b_mov && vis[b_r][b_c] == 1){
directionB[ptr_b++] = -1;
b_mov = 0;
}
if(a_mov && b_mov && a_r == b_r && a_c == b_c){
directionA[ptr_a++] = -1;
directionB[ptr_b++] = -1;
a_mov = 0;
b_mov = 0;
}
if(a_mov) vis[a_r][a_c] = 1;
if(b_mov) vis[b_r][b_c] = 1;
}
}