Untitled

unknown
plain_text
8 days ago
1.6 kB
7
Indexable
Never
```#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;
}
```