Untitled

 avatar
unknown
plain_text
2 years ago
1.6 kB
3
Indexable
#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;
}
Editor is loading...