Untitled

 avatar
unknown
plain_text
a year ago
1.6 kB
10
Indexable
#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x, y;
    int jumps;
};

bool isValid(int x, int y, int m, int n, vector<vector<bool>>& visited) {
    return x >= 0 && x < m && y >= 0 && y < n && !visited[x][y];
}

bool canJump(int x1, int y1, int x2, int y2, int X) {
    return pow(x2 - x1, 2) + pow(y2 - y1, 2) == X * X;
}

int bfs(int m, int n, int X, Point start, Point end) {
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    queue<Point> q;
    q.push({start.x, start.y, 0});
    visited[start.x][start.y] = true;

    while (!q.empty()) {
        Point current = q.front();
        q.pop();

        if (current.x == end.x && current.y == end.y) {
            return current.jumps;
        }

        for (int dx = -X; dx <= X; ++dx) {
            for (int dy = -X; dy <= X; ++dy) {
                if (canJump(current.x, current.y, current.x + dx, current.y + dy, X)) {
                    int newX = current.x + dx;
                    int newY = current.y + dy;
                    if (isValid(newX, newY, m, n, visited)) {
                        visited[newX][newY] = true;
                        q.push({newX, newY, current.jumps + 1});
                    }
                }
            }
        }
    }

    return -1;
}

int main() {
    int m, n, X;
    cin >> m >> n >> X;

    Point start, end;
    cin >> start.x >> start.y;
    cin >> end.x >> end.y;

 
    start.x--; start.y--;
    end.x--; end.y--;

    int result = bfs(m, n, X, start, end);
    cout<<result<<endl;

    return 0;
}
Editor is loading...
Leave a Comment