Untitled
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