Untitled
unknown
plain_text
a year ago
2.8 kB
6
Indexable
#include<iostream> #include<cmath> using namespace std; int T, n, m, p, q, s, t, ri[201], ci[201], map[201][201], visited[201][201]; int dx[4] = {1, -1, -1, 1}; int dy[4] = {1, 1, -1, -1}; const int MAX = 101; struct Queue { int queue[MAX]; int front, rear; Queue() { reset(); } void reset() { front = -1; rear = -1; } void push(int value) { queue[++rear % MAX] = value; } int pop() { return queue[++front % MAX]; } bool isEmpty() { return front == rear; } }; bool isValid(int x, int y) { return x > 0 && x <= n && y > 0 && y <= n; } void bfs(int x, int y) { Queue q; visited[x][y] = 1; q.push(x); q.push(y); while (!q.isEmpty()) { int r = q.pop(); int c = q.pop(); for (int i = 0; i < 4; i++) { for (int j = 1; j <= n; j++) { int nx = r + j * dx[i]; int ny = c + j * dy[i]; if (!isValid(nx, ny)) break; // Đảm bảo nx, ny nằm trong bàn cờ if (map[nx][ny] == 1) break; // Đường đi gặp quân cờ if (visited[nx][ny]) continue; // Ô đã được thăm visited[nx][ny] = 1; if (s == nx && t == ny) { // Đã đến ô đích map[nx][ny] = map[r][c] + 1; return; } // Kiểm tra đường đi từ (r, c) đến (nx, ny) có ô nào có quân cờ không bool hasObstacle = false; int step = abs(nx - r); for (int k = 1; k < step; k++) { int px = r + k * (nx > r ? 1 : -1); int py = c + k * (ny > c ? 1 : -1); if (map[px][py] == 1) { hasObstacle = true; break; } } if (!hasObstacle) { map[nx][ny] = map[r][c] + 1; q.push(nx); q.push(ny); } } } } } int main() { cin >> T; for (int test_case = 1; test_case <= T; ++test_case) { cin >> n >> m >> p >> q >> s >> t; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { map[i][j] = 0; visited[i][j] = 0; } } map[p][q] = 2; for (int i = 1; i <= m; i++) { cin >> ri[i] >> ci[i]; map[ri[i]][ci[i]] = 1; } if (p == s && q == t) { cout << 0 << endl; } else { bfs(p, q); if (map[s][t] == 0) { cout << -1 << endl; } else cout << map[s][t] - 2 << endl; } } return 0; }
Editor is loading...
Leave a Comment