Untitled
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...