Untitled

#include <queue>
#include <iostream>
using namespace std;

#define MAX_N 100

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

// Mảng lưu thông tin về món ăn
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; // Ưu tiên năng lượng nhỏ hơn
        } else if (x.row != y.row) {
            return x.row > y.row; // Nếu năng lượng bằng nhau, ưu tiên row nhỏ hơn
        } else {
            return x.col > y.col; // Nếu row bằng nhau, ưu tiên col nhỏ hơn
        }
    }
};

// Cấu trúc dữ liệu chính
priority_queue<Node, vector<Node>, cmp> pq;
int visited[MAX_N][MAX_N];  // Mảng đánh dấu đã thăm
int cnt[2];                 // Đếm số vi khuẩn
int n;                      // Kích thước của món ăn
int dx[] = {0, 0, 1, -1};   // Di chuyển theo 4 hướng
int dy[] = {1, -1, 0, 0};

// 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;
}

// Khởi tạo
void init(int N, int mDish[MAX_N][MAX_N]) {
    n = N;
    cnt[0] = cnt[1] = 0;
    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 lên một vị trí
int dropMedicine(int mTarget, int mRow, int mCol, int mEnergy) {
    int r = mRow - 1;
    int c = mCol - 1;

    // Nếu vị trí không có vi khuẩn hoặc có vi khuẩn đúng loại
    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;
        }

        // Sử dụng priority_queue thay cho hàng đợi thông thường
        pq = priority_queue<Node, vector<Node>, cmp>();
        visited[r][c] = 1;
        pq.push(dish[r][c]);

        // Khi vẫn còn năng lượng để rải thuốc
        while (mEnergy > 0 && !pq.empty()) {
            Node temp = pq.top();
            pq.pop();

            // Xử lý các ô lân cận
            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] == 0) {
                    visited[x][y] = 1;
                    if (dish[x][y].bacteriumType == 0) {
                        pq.push(dish[x][y]);  // Đưa vào hàng đợi ưu tiên
                    } else if (dish[x][y].bacteriumType == mTarget) {
                        pq.push(dish[x][y]);  // Tiếp tục xử lý các ô đã có vi khuẩn
                    }
                }
            }

            // Thêm năng lượng vào ô tiếp theo
            if (!pq.empty()) {
                Node next = pq.top();
                pq.pop();
                dish[next.row][next.col].bacteriumType = mTarget;
                cnt[mTarget - 1]++;
                mEnergy -= dish[next.row][next.col].energy;
            }
        }
    }

    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;

    // Sử dụng priority_queue để xử lý việc làm sạch
    pq = priority_queue<Node, vector<Node>, cmp>();
    visited[r][c] = 1;
    cnt[type - 1]--;
    dish[r][c].bacteriumType = 0;
    pq.push(dish[r][c]);

    while (!pq.empty()) {
        Node temp = pq.top();
        pq.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] == 0 && dish[x][y].bacteriumType == type) {
                visited[x][y] = 1;
                dish[x][y].bacteriumType = 0;
                cnt[type - 1]--;
                pq.push(dish[x][y]);
            }
        }
    }

    return cnt[type - 1];
}