Untitled

#include <iostream>
#include <unordered_set>
#include <queue>
#include <cstring>
#include <unordered_map>
using namespace std;
   
struct node {
    int seat[101];
    int avail;
} theatre[2001];
   
int visit[101];
   
unordered_map <int, int> m;
   
struct Result {
    int id;
    int num;
};
int n = 0;
   
int dir[4] = { 1,-1,10,-10 };
   
void init(int N)
{
    n = N;
    m.clear();
    for (int i = 1; i <= n; i++)
    {
        theatre[i].avail = 100;
        for (int j = 1; j < 101; j++)
        {
            theatre[i].seat[j] = 0;
        }
    }
    memset(visit, 0, sizeof(visit));
}
   
bool bfs(int tid, int startSeat, int k, int mID) {
    vector<bool> booked(101, false);  // Đánh dấu ghế đã được đặt
    queue<int> q;  // Hàng đợi để BFS
    q.push(startSeat);  // Bắt đầu từ ghế startSeat
    booked[startSeat] = true;  // Đánh dấu ghế startSeat đã được đặt
    int count = 0;  // Đếm số ghế đã đặt
    vector<int> bookedSeats;  // Lưu trữ các ghế đã đặt

    while (!q.empty() && count < k) {  // BFS cho đến khi đủ k ghế hoặc hết ghế để đặt
        int currSeat = q.front();  // Lấy ghế hiện tại từ hàng đợi
        q.pop();
        bookedSeats.push_back(currSeat);  // Thêm ghế hiện tại vào danh sách đã đặt
        count++;  // Tăng số ghế đã đặt

        for (int d = 0; d < 4; ++d) {  // Kiểm tra 4 hướng xung quanh ghế hiện tại
            int nextSeat = currSeat + dir[d];  // Tính toán ghế kế tiếp
            if ((currSeat % 10 == 0 && dir[d] == 1) || (currSeat % 10 == 1 && dir[d] == -1)) {
                continue;  // Bỏ qua nếu vượt qua ranh giới hàng ghế
            }
            if (nextSeat > 0 && nextSeat < 101 && !booked[nextSeat] && theatre[tid].seat[nextSeat] == 0) {
                q.push(nextSeat);  // Thêm ghế hợp lệ vào hàng đợi
                booked[nextSeat] = true;  // Đánh dấu ghế đã được xét
            }
        }
    }

    if (count == k) {
        for (int seat : bookedSeats) {
            theatre[tid].seat[seat] = mID;
        }
        return true;
    }
    return false;
}
Result reserveSeats(int mID, int K)
{
    Result res;
    for (int i = 1; i <= n; i++)
    {
        if (theatre[i].avail >= K)
        {
            memset(visit, 0, sizeof(visit));
            for (int j = 1; j < 101; j++)
            {
                if (visit[j] == 0 && theatre[i].seat[j] == 0 && bfs(i, j, K, mID))
                {
                    theatre[i].avail -= K;
                    m[mID] = i;
                    res.id = i;
                    res.num = j;
                    return res;
                }
            }
        }
    }
    res.id = 0;
    res.num = 0;
    return res;
}
    
Result cancelReservation(int mID)
{
    int sum = 0;
    int tid = m[mID];
    int cnt = 0;
    for (int i = 1; i < 101; i++)
    {
        if (theatre[tid].seat[i] == mID)
        {
            sum += i;
            theatre[tid].seat[i] = 0;
            cnt++;
        }
    }
    m[mID] = 0;
    theatre[tid].avail += cnt;
    Result res;
    res.id = tid;
    res.num = sum;
    return res;
}