Untitled

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;
class Bacteria {
    int type;
    int row;
    int col;
    int energy;
      
    public Bacteria(int r, int c, int e) {
          
        type = 0;
        row = r;
        col = c;
        energy = e;
          
    }
}
class UserSolution {
  
      
    int visit[][] = new int[101][101];
    int N;
    int X[] = {-1,0,1,0};
    int Y[] = {0, -1, 0, 1};
    PriorityQueue<Bacteria> Heap = new PriorityQueue<Bacteria>((o1, o2) -> {
    	if (o1.energy == o2.energy) {
            if (o1.row == o2.row) {
                return o1.col - o2.col;
            } 
              
            return o1.row - o2.row;
          
        }
        return o2.energy - o1.energy;
    });;
    Bacteria[][] map = new Bacteria[101][101];
    int count[];
    ArrayDeque<Bacteria> que = new ArrayDeque<>();
    int time;
 
      
    void init(int n, int mDish[][]) {
        N = n;
        count = new int[3];
        Heap.clear();
        que.clear();
        time = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                visit[i][j] = 0;  
                map[i][j] = new Bacteria(i, j, mDish[i][j]);
            }
        }
    }
  
    int dropMedicine(int mtype, int mRow, int mCol, int mEnergy){
        int row = mRow - 1;
        int col = mCol - 1;
        time++;
        Bacteria b = map[row][col];
        if ((b.type == 1 && mtype == 2) || (b.type == 2 && mtype == 1)) {
            return count[mtype];
        }
        Heap.clear();
        Heap.add(b);
        que.clear();
          
        while (mEnergy > 0 && !Heap.isEmpty()) {
            Bacteria b1 = Heap.poll();
            if (b1.type == 0) {
                mEnergy = mEnergy - b1.energy;
                b1.type = mtype;
                count[mtype]++;
                  
            }
            BFS(mtype, b1);
        }
        return count[mtype];
    }
  
    private void BFS(int mtype, Bacteria b1) {
         
        que.add(b1);
        visit[b1.row][b1.col] = time;
        while (!que.isEmpty()) {
            Bacteria b2 = que.pollFirst();
            for (int i = 0; i < 4; i++) {
                int r = b2.row + X[i];
                int c = b2.col + Y[i];
                  
                if (r >= 0 && r < N && c >=0 && c < N && visit[r][c] < time
                        && (map[r][c].type == 0 || map[r][c].type == mtype)) {
                    Bacteria b3 = map[r][c];
                    visit[r][c] = time;
                    if (b3.type == mtype) {
                        que.add(b3);
                    } else {
                        Heap.add(b3);
                    }
                      
                }
            }
        }
          
    }
  
    int cleanBacteria(int mRow, int mCol){
        int row = mRow - 1;
        int col = mCol - 1;
        time++;
        Bacteria b = map[row][col];
          
        if (b.type == 0) {
            return -1;
        }
          
        que.clear();
        que.add(b);
          
        count[b.type]--;
        int type = b.type;
        b.type = 0;
        visit[b.row][b.col] = time;
        while (!que.isEmpty()) {
            Bacteria b1 = que.pollFirst();
            for (int i = 0; i < 4; i++) {
                int r = b1.row + X[i];
                int c = b1.col + Y[i];
                //System.out.println("r : "+ r + "c : "+ c);
                if (r >=0 && r < N && c >= 0 && c < N && map[r][c].type == type && visit[r][c] < time) {
                    Bacteria b2 = map[r][c];
                    visit[r][c] = time;
                    que.add(b2);
                    count[b2.type]--;
                    b2.type = 0;
                }
            }
        }
          
        return count[type];
    }
}

// my way
#include <deque>
using namespace std;
#define MAX 10000
int N;
int visit[101][101];
int visitID = 0;
int Total[3];
int DX[4] = {-1, 0, 1, 0};
int DY[4] = {0, 1, 0, -1};


struct Cell{
	int row,col;
	int energy;
	int mTarget;
	bool operator>(Cell &cell){
		if(energy==cell.energy){
        if(row == cell.row) return col < cell.col;
            return row < cell.row;
        }
        return energy > cell.energy;
	}
}map[101][101];

deque<Cell> q;


struct Heap{
	int nHeap;
	Cell heap[MAX];
void swap(Cell* x, Cell* y) {
    Cell temp = *x;
    *x = *y;
    *y = temp;
}
  
void up_heap(int i) {
    if (i == 1 || heap[i / 2] > heap[i]) return; 
     
    swap(&heap[i], &heap[i / 2]);
 
    up_heap(i / 2); 
}
void down_heap(int i) 
{
    // recall  
    int left = i * 2 ;
     
    // come to end of branch
    if (left > nHeap) 
        return; 
         
    // choose greater child
    if (left < nHeap && heap[left + 1] > heap[left]) 
        left++;
     
    if (heap[left] > heap[i]) // if child > parent -> swap
    {
        swap(&heap[i], &heap[left]);
        down_heap(left); // recursive to lower branch
    }
}
 
void push(Cell value) {
    if (nHeap >= MAX)
        return;
    else {
        heap[++nHeap] = value;
        up_heap(nHeap);
    }
}
void pop() {
    if (nHeap <= 0)
        return;
    else
    {
        
        heap[1] = heap[nHeap];
		nHeap--;
        down_heap(1);
    }
}
}heap;

 
void init(int n, int mDish[100][100]) {
     N = n;
	 heap.nHeap = 0;
     Total[0] = Total[1] = Total[2] = 0;
	 q.clear();
	 visitID = 0;
    for ( int i=1; i<=N; i++) {
		for ( int j=1; j<=N; j++) {
			visit[i][j] = 0;
			map[i][j].row = i-1;
			map[i][j].col = j-1;
			map[i][j].energy = mDish[i-1][j-1];
			map[i][j].mTarget = 0;
		}
	}
}

bool isValid(int r, int c) {
        return r > 0 && r <= N && c > 0 && c <= N && visit[r][c] != visitID;
    }

void DFS(Cell cell, int type) {
        visit[cell.row][cell.col] = visitID;
            for (int i = 0; i < 4; i++) {
                int r = cell.row + DX[i], c = cell.col + DY[i];
                if (isValid(r, c)) {
                    visit[r][c] = visitID;
                    if (map[r][c].mTarget == 0) DFS(map[r][c],type);
                    else if (map[r][c].mTarget == type) DFS(map[r][c],type);
                }
            }
        }

void BFS(Cell cell, int type) {
		//f = r = -1;
        visit[cell.row][cell.col] = visitID;
        q.push_back(cell);
        while (!q.empty()) {
            Cell cur = q.front();
			q.pop_front();
            for (int i = 0; i < 4; i++) {
                int r = cur.row + DX[i], c = cur.col + DY[i];
                if (isValid(r, c)) {
                    visit[r][c] = visitID;
					if (map[r][c].mTarget == 0) heap.push(map[r][c]);
                    else if (map[r][c].mTarget == type) q.push_back(map[r][c]);
                }
            }
        }
    }

int dropMedicine(int mTarget, int mRow, int mCol, int mEnergy) {
        heap.nHeap = 0;
        Cell cell = map[mRow][mCol];
        if (cell.mTarget != 0 && cell.mTarget != mTarget) return Total[mTarget];
        visitID++;
        heap.push(cell);
        while (mEnergy > 0 && heap.nHeap > 0) {
            Cell cur = heap.heap[1]; 
				heap.pop();
            if (cur.mTarget == 0) {
                cur.mTarget = mTarget;
                mEnergy -= cur.energy;
                Total[mTarget]++;
            }
            BFS(cur, mTarget);
        }
        return Total[mTarget];
    }


	int cleanBacteria(int mRow, int mCol) {
        Cell cell = map[mRow][mCol];
        if (cell.mTarget == 0) return -1;
        int type = cell.mTarget;
        visit[cell.row][cell.col] = ++visitID;
         q.push_back(cell);
        while (!q.empty()) {
            Cell cur = q.front();
			q.pop_front();
            cur.mTarget = 0;
            Total[type]--;
 
            for (int i = 0; i < 4; i++) {
                int r = cur.row + DX[i], c = cur.col + DY[i];
                if (isValid(r, c) && map[r][c].mTarget == type) {
                    visit[r][c] = visitID;
                     q.push_back(map[r][c]);
                }
            }
        }
        return Total[type];
    }