Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.0 kB
1
Indexable
Never
#include <stdio.h>
#define MAX_N 202
#define INF 1000000

int dy[] = {-1, 1, 1, -1};
int dx[] = {1, 1, -1, -1};

int map[MAX_N][MAX_N];
int curDir[MAX_N][MAX_N];
int sR, sC, eR, eC;
int N, M;

int Q[MAX_N * MAX_N];
int front, rear;

void BFS()
{
	int r, c, nextR, nextC;
	front = 0; rear = -1;
	for (int d = 0; d < 4; d++) {
		nextR = sR + dy[d];
		nextC = sC + dx[d];
		if (nextR < 0 || nextR == N || nextC < 0 || nextC == N)
				continue;
		if (map[nextR][nextC] != 0) {
			map[nextR][nextC] = 1;
			curDir[nextR][nextC] = d;
			Q[++rear] = nextR * N + nextC;
		}
	}
	int nextCnt;
	
	while (front <= rear) {
		r = Q[front] / N;
		c = Q[front++] % N;
		for (int d = 0; d < 4; d++) {
			nextR = r + dy[d];
			nextC = c + dx[d];
			if (nextR < 0 || nextR == N || nextC < 0 || nextC == N)
				continue;

			nextCnt = d == curDir[r][c] ? map[r][c] : map[r][c] + 1;
			if (map[nextR][nextC] > nextCnt) {
				map[nextR][nextC] =  nextCnt;
				curDir[nextR][nextC] = d;
				Q[++rear] = nextR * N + nextC;				
			}			
		}
	}
}

int main() {
	int T;
	int tmpR, tmpC;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		scanf("%d%d%d%d%d%d", &N, &M, &sR, &sC, &eR, &eC);
		sR = N - sR;
		eR = N - eR;
		sC--;
		eC--;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				map[i][j] = INF;
		map[sR][sC] = 1;
		for (int i = 0; i < M; i++) {
			scanf("%d%d", &tmpR, &tmpC);
			map[N - tmpR][tmpC - 1] = 0;
		}

		BFS();
		
		printf("%d\n", map[eR][eC] == INF ? -1 : map[eR][eC]);
	}

	return 0;
}




15
5 5 5 5 5 3
1 2
1 5
2 2
4 2
4 3
8 4 2 5 5 4
3 6
4 3
4 5
6 3
10 5 6 5 1 8
2 9
5 6
6 7
7 4
8 7
12 0 3 4 10 3
14 7 6 1 7 14
10 3
2 9
4 12
8 3
5 2
6 3
12 3
16 7 4 13 16 15
6 13
5 12
3 14
9 8
11 16
3 12
6 15
17 9 12 14 15 7
14 16
11 13
13 13
10 16
11 15
15 10
15 13
16 2
17 9
18 10 12 14 3 1
11 13
11 15
14 16
4 13
6 6
13 15
13 12
11 4
10 10
17 6
20 4 19 13 15 5
20 14
18 14
18 12
19 10
20 7 15 9 2 14
6 18
11 5
17 11
14 18
14 8
16 8
14 10
40 10 38 16 36 4
40 18
37 15
39 15
36 18
39 17
35 17
27 17
29 9
31 9
38 32
80 20 25 15 19 65
27 17
24 14
26 14
24 16
25 17
27 10
30 19
38 13
41 31
47 37
47 79
49 20
50 35
51 51
60 80
68 1
69 9
71 50
72 27
79 42
100 30 25 35 90 48
27 37
24 34
26 34
27 37
23 37
18 57
20 11
23 89
29 24
29 33
31 57
36 13
41 87
44 37
44 84
46 12
50 10
51 9
54 81
58 69
64 74
66 39
78 31
80 81
82 22
85 43
87 26
89 50
94 99
99 67
120 50 28 99 68 77
2 68
3 31
3 58
4 1
6 60
11 63
15 83
16 30
23 4
23 90
28 81
30 37
35 25
36 43
37 69
37 108
39 3
45 31
46 109
46 118
47 91
51 106
52 23
55 58
56 102
59 12
59 68
63 44
64 67
65 8
65 80
68 32
72 98
73 75
78 111
82 95
85 38
85 120
86 117
88 9
88 116
92 58
102 81
104 19
104 103
107 27
116 55
116 66
117 51
120 90
200 0 30 148 173 79