Untitled

 avatar
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