Untitled
unknown
plain_text
a year ago
2.2 kB
6
Indexable
#include <iostream> using namespace std; struct Point { int x, y; Point(int _x, int _y) : x(_x), y(_y) {} }; struct Queue { Point elements[1000000]; int front, rear; Queue() : front(0), rear(-1) {} void push(Point p) { elements[++rear] = p; } Point pop() { return elements[front++]; } bool isEmpty() { return front > rear; } }; int T, n, m, p, q, s, t; int board[201][201]; bool visited[201][201]; int dx[4] = {1, -1, -1, 1}; int dy[4] = {1, 1, -1, -1}; bool isValid(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= n; } bool canMove(int x, int y) { for (int i = 1; i <= m; i++) { int r = ri[i], c = ci[i]; if ((x - p) * (c - q) == (y - q) * (r - p) && (x - p) * (x - r) + (y - q) * (y - c) < (x - r) * (x - r) + (y - c) * (y - c)) return false; } return true; } void push(Point p, Queue &q) { q.push(p); } Point pop(Queue &q) { return q.pop(); } bool isEmpty(Queue &q) { return q.isEmpty(); } int bfs() { Queue q; push(Point(p, q), q); visited[p][q] = true; int level = 0; while (!isEmpty(q)) { int size = q.rear - q.front + 1; while (size--) { Point point = pop(q); int x = point.x, y = point.y; if (x == s && y == t) return level; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (isValid(nx, ny) && !visited[nx][ny] && canMove(nx, ny)) { visited[nx][ny] = true; push(Point(nx, ny), q); } } } level++; } return -1; } int main() { cin >> T; while (T--) { cin >> n >> m >> p >> q >> s >> t; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { board[i][j] = 0; visited[i][j] = false; } } for (int i = 1; i <= m; i++) { int r, c; cin >> r >> c; board[r][c] = 1; } cout << bfs() << endl; } return 0; }
Editor is loading...
Leave a Comment