# Untitled

unknown
plain_text
8 days ago
2.9 kB
4
Indexable
Never
```#include <iostream>
#include <vector>
#include <queue>
#include <climits>
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;

for(int i = fx+1;i<m;i++){
fireTime[i][fy] = fireTime[i-1][fy] + 1;
}
for(int i = fx-1;i>=0;i--){
fireTime[i][fy] = fireTime[i+1][fy] + 1;
}
for(int i = fy+1;i<n;i++){
fireTime[fx][i] = fireTime[fx][i-1] + 1;
}
for(int i = fy-1;i>=0;i--){
fireTime[fx][i] = fireTime[fx][i+1] + 1;
}
// make everythin else INT_MAX
for(int i = 0; i<m; i++){
for(int j = 0; j<n; j++){
if(fireTime[i][j] == -1){
fireTime[i][j] = INT_MAX;
}
}
}
}

// 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  >> fx >> fy >> ix >> iy >> jx >> jy;

vector<vector<int>> fireTime(m, vector<int>(n, -1));

if (canReach(fireTime, ix, iy, jx, jy, m, n)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}