Untitled
unknown
plain_text
a year ago
2.5 kB
8
Indexable
#include <iostream> #include <vector> #include <queue> using namespace std; struct Point { int x, y, time; }; // Directions for moving in the grid int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; // Function to check if a point is inside the grid bool isValid(int x, int y, int m, int n) { return (x >= 0 && x < m && y >= 0 && y < n); } // BFS function to calculate the minimum time to reach each cell by fire void fireSpread(vector<vector<int>>& fireTime, int fx, int fy, int m, int n) { queue<Point> q; q.push({fx, fy, 0}); fireTime[fx][fy] = 0; while (!q.empty()) { Point cur = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; if (isValid(nx, ny, m, n) && fireTime[nx][ny] == -1) { fireTime[nx][ny] = cur.time + 1; q.push({nx, ny, cur.time + 1}); } } } } // BFS function to check if Jimmy can reach the destination before the fire bool canReach(vector<vector<int>>& fireTime, int ix, int iy, int jx, int jy, int m, int n) { vector<vector<int>> jimmyTime(m, vector<int>(n, -1)); queue<Point> q; q.push({ix, iy, 0}); jimmyTime[ix][iy] = 0; while (!q.empty()) { Point cur = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; if (isValid(nx, ny, m, n) && jimmyTime[nx][ny] == -1) { int nextTime = cur.time + 1; if (nextTime < fireTime[nx][ny]) { jimmyTime[nx][ny] = nextTime; q.push({nx, ny, nextTime}); if (nx == jx && ny == jy) { return true; } } } } } return false; } int main() { int m, n, t; cin >> m >> n >> t; for (int i = 0; i < t; ++i) { int ix, iy, jx, jy, fx, fy; cin >> ix >> iy >> jx >> jy >> fx >> fy; vector<vector<int>> fireTime(m, vector<int>(n, -1)); fireSpread(fireTime, fx, fy, m, n); if (canReach(fireTime, ix, iy, jx, jy, m, n)) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return 0; }
Editor is loading...
Leave a Comment