50122. Knights' Tour
難度：4/5 Used Time: 19:161
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
76
77
78
79
80
81
82
83#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define max(a,b) ((a)>(b)?(a):(b))
typedef struct{
int x;
int y;
int step;
char moving;
}pt;
int n, m;
int moving_cnt;
pt kt[10005] = {0};
int ans[100][100] = {0};
int dx[9] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
int dy[9] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
static inline int is_valid(int x, int y){
return x >= 0 && y >= 0 && x < n && y < n && ans[x][y] == 0;
}
void ipt(){
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++){
scanf("%d %d", &kt[i].x, &kt[i].y);
ans[kt[i].x][kt[i].y] = 10000 * i;
kt[i].step = 0;
kt[i].moving = 1;
}
moving_cnt = m;
}
static inline int count_steps(int x, int y){
int cnt = 0;
for(int i = 1; i <= 8; i++){
int a_x = x + dx[i], a_y = y + dy[i];
if(is_valid(a_x, a_y)) cnt++;
}
return cnt;
}
int choose_step(pt* k){
int min_idx = -1, min_cnt = INT_MAX;
for(int i = 1; i <= 8; i++){
int mov_x = k->x + dx[i], mov_y = k->y + dy[i];
if(!is_valid(mov_x, mov_y)) continue;
int cnt = count_steps(mov_x, mov_y);
if(cnt < min_cnt) min_idx = i, min_cnt = cnt;
}
return min_idx;
}
void solve(){
while(moving_cnt > 0){
for(int i = 1; i <= m; i++){ pt* now_k = &kt[i];
if(now_k->moving == 0) continue;
int step_idx = choose_step(now_k);
if(step_idx == -1){
now_k->moving = 0;
moving_cnt--;
}
else{
now_k->x += dx[step_idx];
now_k->y += dy[step_idx];
now_k->step++;
ans[now_k->x][now_k->y] = 10000 * i + now_k->step;
}
}
}
}
int main(){
ipt();
solve();
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
printf("%d%c", ans[i][j], (j == n - 1) ? '\n' : ' ');
}
}
}