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++;
    
    // Khởi tạo giá trị cho mảng previous
    for(int i = 0; i < MAX_BOX; i++) {
        previous[i] = -1;
    }

    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]) {
            if(previous[boxId] == -1) { // Chỉ cập nhật nếu chưa đi qua
                previous[boxId] = boxCur;
                
                if(boxId == mIdB) {
                    int current = boxId;
                    while(current != mIdA) {
                        history.push_back(current);
                        current = previous[current];
                    }
                    history.push_back(mIdA);

                    // Đảo ngược lịch sử để in đúng thứ tự
                    reverse(history.begin(), history.end());
                    
                    for(auto it : history) {
                        cout << it << " ";
                    }
                    cout << endl;
                    
                    return cnt;
                }
                
                if(visit[boxId] < step) {
                    pq.push(make_pair(cnt + 1, boxId));
                    visit[boxId] = step;
                }
            }
        }
    }
    
    return -1;
}