Untitled

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

#define MAX_HEIGHT 1001
#define MAX_WIDTH 200001
#define MAX_BOX 10001
#define INF 99999999

struct Space {
	int id, row;
	bool haveExit;
};

Space space[MAX_WIDTH];
vector<int> graph[MAX_BOX];

int visit[MAX_BOX];
int step = 0;
void init(int mH, int mW)
{
	for(int i = 0; i < mW; i++) {
		space[i].id = -1;
		space[i].row = mH;
		space[i].haveExit = 0;
	}
	for(int i = 0; i < MAX_BOX; i++) {
		graph[i].clear();
		visit[i] = 0;
	}
}

int dropBox(int mId, int mLen, int mExitA, int mExitB, int mCol)
{
	int rowTarget = INF;
	for(int i = mCol; i < mCol + mLen; i++) {
		rowTarget = min(rowTarget, space[i].row);
	}
	rowTarget--;

	if(space[mCol + mExitA].row == rowTarget + 1 && space[mCol + mExitA].id != -1) { // Check exitA of above rowtarget box(mId)
		graph[mId].push_back(space[mCol + mExitA].id);
	}

	if(space[mCol + mExitB].row == rowTarget + 1 && space[mCol + mExitB].id != -1) { // Check exitB of above rowtarget box(mId)
		graph[mId].push_back(space[mCol + mExitB].id);
	}

	if(mCol != 0 && space[mCol - 1].row == rowTarget) { // Check left box(mID)
		graph[mId].push_back(space[mCol - 1].id);
		graph[space[mCol - 1].id].push_back(mId);
	}

	if(space[mCol + mLen].row == rowTarget) { // Check right box(mId)
		graph[mId].push_back(space[mCol + mLen].id);
		graph[space[mCol + mLen].id].push_back(mId);
	}

	for(int i = mCol; i < mCol + mLen; i++) {
		if(space[i].row == rowTarget + 1 && space[i].haveExit) {
			graph[space[i].id].push_back(mId);
		}
		// Update id, rowMax, haveExit at all position of box(mId) in space
		space[i].id = mId;
		space[i].row = rowTarget;
		if(i == mCol + mExitA || i == mCol + mExitB) {
			space[i].haveExit = 1;
		} else {
			space[i].haveExit = 0;
		}
	}
	return rowTarget;
}
struct cmp {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {

        return a.first > b.first;
    }
};


int explore(int mIdA, int mIdB) {
	vector<int> history;
	int previous[MAX_BOX];
	step++;
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	pq.push(make_pair(1, mIdA));
	previous[mIdA] = mIdA;
	while(!pq.empty()) {
		pair<int, int> temp = pq.top();
		pq.pop();
		int cnt = temp.first;
		int boxCur = temp.second;
		for(int boxId : graph[boxCur]) {
			previous[boxId] = boxCur;
			if(boxId == mIdB) {
				int current = boxId;
				while(current != mIdA) {
					history.push_back(current);
					current = previous[current];
				}
				history.push_back(mIdA);
				//reverse(history.begin, history.end);
				for(auto it:history) {
					cout<<it<<" ";
				}
				return cnt;
			}
			if(visit[boxId] < step) {
				pq.push(make_pair(cnt+1, boxId));
				visit[boxId] = step;
			}
		}
	}
	return -1;
}