# Untitled

unknown
plain_text
9 days ago
2.5 kB
7
Indexable
Never
```#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  >> fx >> fy >> ix >> iy >> jx >> jy;

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