Untitled

#include<iostream>
#include<queue>

using namespace std;

struct Bacteria {
    int id;
    int size;
    int time;
} Bacteria_pool[3003];

int Map[202][202];
int N;

struct Result {
    int row;
    int col;
};

int ts = 0;
int visited[202][202];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };

// Cấu trúc node cho hàng đợi ưu tiên
struct node {
    int x, y, dis;
};

// Hàm so sánh cho priority_queue
struct cmp {
    bool operator()(const node& a, const node& b) const {
        if (a.dis == b.dis) {
            if (a.x == b.x) {
                return a.y > b.y;
            }
            return a.x > b.x;
        }
        return a.dis > b.dis;
    }
};

// Khởi tạo bản đồ
void init(int N) {
    ::N = N;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            Map[i][j] = 0;
        }
    }
}

// Hàm enQueue để thêm phần tử vào hàng đợi
void enQueue(queue<pair<int, int>>& q, int x, int y) {
    q.push({ x, y });
}

// Hàm deQueue để lấy phần tử đầu tiên ra khỏi hàng đợi
pair<int, int> deQueue(queue<pair<int, int>>& q) {
    pair<int, int> front = q.front();
    q.pop();
    return front;
}

// Kiểm tra xem vi khuẩn có thể lan từ vị trí (x, y)
int check(int x, int y, int stime, Bacteria b) {
    int w = 0, r = 0;
    if (Bacteria_pool[Map[x][y]].time > stime)
        return 0;
    
    queue<pair<int, int>> q;  // Sử dụng hàng đợi pair<int, int>
    enQueue(q, x, y);
    visited[x][y] = ++ts;

    while (!q.empty()) {
        pair<int, int> temp = deQueue(q);

        for (int i = 0; i < 4; i++) {
            int nx = temp.first + dx[i];
            int ny = temp.second + dy[i];

            // Kiểm tra vị trí hợp lệ
            if (nx < 1 || nx > N || ny < 1 || ny > N || visited[nx][ny] == ts)
                continue;

            if (Bacteria_pool[Map[nx][ny]].time <= stime) {
                visited[nx][ny] = ts;
                enQueue(q, nx, ny);
                if (++w >= b.size) return 1;
            }
        }
    }
    return 0;
}

// Đặt vi khuẩn lên bản đồ
Result putBacteria(int mTime, int mRow, int mCol, Bacteria mBac) {
    if (!check(mRow, mCol, mTime, mBac))
        return { 0, 0 };
    
    int count = mBac.size;
    priority_queue<node, vector<node>, cmp> pq;
    pq.push({ mRow, mCol, 0 });

    visited[mRow][mCol] = ++ts;
    Bacteria_pool[mBac.id] = { mBac.id, mBac.size, mTime + mBac.time };

    while (!pq.empty()) {
        node t = pq.top();
        pq.pop();

        Map[t.x][t.y] = mBac.id;
        if (--count == 0) return { t.x, t.y };

        for (int i = 0; i < 4; i++) {
            int nx = t.x + dx[i];
            int ny = t.y + dy[i];
            
            if (nx < 1 || ny < 1 || nx > N || ny > N || visited[nx][ny] == ts)
                continue;

            if (Bacteria_pool[Map[nx][ny]].time <= mTime) {
                visited[nx][ny] = ts;
                pq.push({ nx, ny, abs(mRow - nx) + abs(mCol - ny) });
            }
        }
    }
    return { 0, 0 };
}

// Kiểm tra vi khuẩn tại một ô cụ thể
int checkCell(int mTime, int mRow, int mCol) {
    return Bacteria_pool[Map[mRow][mCol]].time <= mTime ? 0 : Bacteria_pool[Map[mRow][mCol]].id;
}

// Diệt vi khuẩn tại vị trí (mRow, mCol)
int killBacteria(int mTime, int mRow, int mCol) {
    int res = checkCell(mTime, mRow, mCol);
    if (res)
        Bacteria_pool[Map[mRow][mCol]].time = -1;
    return res;
}