Untitled

 avatar
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