Untitled

#define MAX_N 100
#include <queue>
#include <iostream>
using namespace std;

struct Node {
    int row;
    int col;
    int energy;
    int bacteriumType;
};

Node dish[MAX_N][MAX_N];

// Trình so sánh để sử dụng trong priority_queue
struct cmp {
    bool operator() (Node x, Node y) {
        if (x.energy != y.energy) {
            return x.energy < y.energy;
        } else if (x.row != y.row) {
            return x.row > y.row;
        } else
            return x.col > y.col;
    }
};

int n, cnt[2], point;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int visited[MAX_N][MAX_N];
priority_queue<Node, vector<Node>, cmp> priorityQueue;
queue<Node> q; // Thay thế hàng đợi thủ công bằng queue của thư viện chuẩn

// Kiểm tra xem vị trí (a, b) có hợp lệ trong mảng không
bool checked(int a, int b) {
    return a >= 0 && a < n && b >= 0 && b < n;
}

// Hàm khởi tạo
void init(int N, int mDish[MAX_N][MAX_N]) {
    n = N;
    cnt[0] = cnt[1] = point = 0;
    while (!q.empty()) q.pop(); // Xóa các phần tử trong hàng đợi
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dish[i][j].row = i;
            dish[i][j].col = j;
            dish[i][j].energy = mDish[i][j];
            dish[i][j].bacteriumType = 0;
            visited[i][j] = 0;
        }
    }
}

// Hàm rải thuốc
int dropMedicine(int mTarget, int mRow, int mCol, int mEnergy) {
    int r = mRow - 1;
    int c = mCol - 1;
    if (dish[r][c].bacteriumType == 0 || dish[r][c].bacteriumType == mTarget) {
        if (dish[r][c].bacteriumType == 0) {
            dish[r][c].bacteriumType = mTarget;
            cnt[mTarget - 1]++;
            mEnergy -= dish[r][c].energy;
        }

        point++;
        priorityQueue = priority_queue<Node, vector<Node>, cmp>();
        while (!q.empty()) q.pop(); // Xóa hàng đợi cũ

        visited[r][c] = point;
        q.push(dish[r][c]);

        while (mEnergy > 0) {
            while (!q.empty()) {
                Node temp = q.front();
                q.pop();
                for (int i = 0; i < 4; i++) {
                    int x = temp.row + dx[i];
                    int y = temp.col + dy[i];
                    if (checked(x, y) && visited[x][y] < point) {
                        visited[x][y] = point;
                        if (dish[x][y].bacteriumType == 0) {
                            priorityQueue.push(dish[x][y]);
                        } else if (dish[x][y].bacteriumType == mTarget) {
                            q.push(dish[x][y]);
                        }
                    }
                }
            }

            if (!priorityQueue.empty()) {
                Node temp = priorityQueue.top();
                priorityQueue.pop();
                dish[temp.row][temp.col].bacteriumType = mTarget;
                cnt[mTarget - 1]++;
                mEnergy -= dish[temp.row][temp.col].energy;
                q.push(dish[temp.row][temp.col]);
            } else {
                break;
            }
        }
    }
    return cnt[mTarget - 1];
}

// Hàm làm sạch vi khuẩn
int cleanBacteria(int mRow, int mCol) {
    int r = mRow - 1;
    int c = mCol - 1;
    int type = dish[r][c].bacteriumType;
    if (type == 0) return -1;

    point++;
    visited[r][c] = point;
    cnt[type - 1]--;
    dish[r][c].bacteriumType = 0;
    q.push(dish[r][c]);

    while (!q.empty()) {
        Node temp = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x = temp.row + dx[i];
            int y = temp.col + dy[i];
            if (checked(x, y) && visited[x][y] < point && dish[x][y].bacteriumType == type) {
                dish[x][y].bacteriumType = 0;
                cnt[type - 1]--;
                visited[x][y] = point;
                q.push(dish[x][y]);
            }
        }
    }
    return cnt[type - 1];
}