Untitled

#define MAX_N 100
#include <queue>
  
using namespace std;
  
struct Node{
    int row;
    int col;
    int energy;
    int bacteriumType;
};
Node dish[MAX_N][MAX_N];
Node queueN[MAX_N * MAX_N];
  
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], front, rear, 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;
  
void initQueue(){
    front = rear = -1;
}
  
void enQueue(Node a){
    front++;
    queueN[front] = a;
}
  
Node deQueue(){
    rear++;
    return queueN[rear];
}
  
bool isEmpty(){
    if(front == rear)
        return true;
    return false;
}
 
bool checked(int a, int b){
    if(a >= 0 && a < n && b >= 0 && b < n)
        return true;
    return false;
}
 
void init(int N, int mDish[MAX_N][MAX_N]){
    n = N;
    cnt[0] = cnt[1] = point = 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;
        }
    }
}
  
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>();
  
        initQueue();
        visited[r][c] = point;
        enQueue(dish[r][c]);
  
        while (mEnergy > 0){
            while (!isEmpty()){
                Node temp = deQueue();
                int i=0;
                while(i < 4){
                    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)
                            enQueue(dish[x][y]);
                    }
                    i++;
                }
            }
  
            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;
                enQueue(dish[temp.row][temp.col]);
            }
			
            else
                break;
        }
    }
    int res = cnt[mTarget - 1];
    return res;
}
  
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;
    initQueue();
    point++;
    visited[r][c] = point;
    cnt[type - 1]--;
    dish[r][c].bacteriumType = 0;
    enQueue(dish[r][c]);
    while (!isEmpty()){
        Node temp = deQueue();
        int i = 0;
        while(i < 4){
            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;
                enQueue(dish[x][y]);
            }
            i++;
        }
    }
    int res = cnt[type - 1];
    return res;
}
/*
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>
#include <iostream>
using namespace std;
#define MAX_N 100

extern void init(int N, int mDish[MAX_N][MAX_N]);
extern int dropMedicine(int mTarget, int mRow, int mCol, int mEnergy);
extern int cleanBacteria(int mRow, int mCol);

#define CMD_INIT 100
#define CMD_DROP 200
#define CMD_CLEAN 300

static bool run()
{
    int query_num;
    scanf("%d", &query_num);

    int ret, ans;
    bool ok = false;
    static int dish[MAX_N][MAX_N];

    for (int q = 0; q < query_num; q++)
    {
        int query;
        scanf("%d", &query);

        if (query == CMD_INIT)
        {
            int N;
            scanf("%d", &N);
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    scanf("%d", &dish[i][j]);
                }
            }
            init(N, dish);
            ok = true;
        }
        else if (query == CMD_DROP)
        {
            int mTarget;
            int mRow, mCol;
            int mEnergy;
            scanf("%d %d %d %d", &mTarget, &mRow, &mCol, &mEnergy);
            ret = dropMedicine(mTarget, mRow, mCol, mEnergy);
            scanf("%d", &ans);
            if (ans != ret)
            {
				cout<<"TC: "<<q<<" "<<ret<<" "<<ans<<endl;
                ok = false;
            }
        }
        else if (query == CMD_CLEAN)
        {
            int mRow, mCol;
            scanf("%d %d", &mRow, &mCol);
            ret = cleanBacteria(mRow, mCol);
            scanf("%d", &ans);
            if (ans != ret)
            {
                ok = false;
            }
        }
    }
    return ok;
}

int main()
{
    setbuf(stdout, NULL);
    freopen("sample_input.txt", "r", stdin);
    int T, MARK;
    scanf("%d %d", &T, &MARK);

    for (int tc = 1; tc <= T; tc++)
    {
        int score = run() ? MARK : 0;
        printf("#%d %d\n", tc, score);
    }
    return 0;
}
1 100
2
100 6
3 3 5 1 1 1
4 2 4 2 2 1
1 1 1 3 2 2
3 2 2 5 2 1
1 5 2 1 1 2
2 1 2 1 3 3
200 1 3 4 19 5
200 1 4 4 14 10
200 1 6 3 3 12
200 1 3 6 10 16
200 2 1 5 20 4
200 2 1 2 7 4
200 2 1 5 5 4
200 1 5 5 5 19
300 2 4 3
300 2 6 0
300 6 6 0
200 2 2 2 7 3
200 2 3 6 7 6
200 2 5 3 13 11
200 2 3 3 13 15
200 2 3 1 3 17
200 2 2 5 13 26
300 5 5 -1
200 2 6 6 9 30
200 1 6 1 20 3


*/