Untitled

#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <cstring>

using namespace std;

struct cmp{
	bool operator() (pair<int, int> a, pair<int, int>b) {
		if(a.first == b.first) {
			return a.second > b.second;
		}
		return a.first > b.first;
	}
};

struct Result{
	int id;
	int num;
};
struct Theater{
	int seat[101][101];
	int slot;
} theater[2001];
int visit[101][101];
int n;
int map[101][101];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
unordered_map<int, int> mp;

void init(int N) 
{
	int start = 1;
	for(int i=1; i<=100; i++) {
		for(int j=1; j<=100; j++) {
			map[i][j] = start++;
		}
	}
	n = N;
	mp.clear();
	for(int i=1; i<=n; i++) {
		theater[i].slot = 100;
		for(int j=1; j<=100; j++) {
			for(int k=1; k<=100; k++) {
				theater[i].seat[j][k] = 0;
			}
		}
	}
}

bool bfs(int tId, int seatX, int seatY, int k, int mId) {
	int cnt = 0;
	int book[101][101];
	memset(book, 0, sizeof(book));
	book[seatX][seatY] = 1;
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	pq.push(make_pair(seatX, seatY));
	while(!pq.empty()) {
		pair<int, int> curSeat = pq.top();
		pq.pop();
		cnt++;
		if(cnt == k) {
			break;
		}
		for(int k=0; k<4; k++) {
			int nx = curSeat.first + dx[k];
			int ny = curSeat.second + dy[k];
			if(nx > 0 && nx < 101 && ny > 0 && ny < 101) {
				if(!visit[nx][ny] && !book[nx][ny] && !theater[tId].seat[nx][ny]) {
					pq.push(make_pair(nx, ny));
					visit[nx][ny] = 1;
				}
			}
		}
	}
	if(cnt == k) {
		for(int i=1; i<101; i++) {
			for(int j=1; j<=101; j++) {
				if(book[i][j] == 1) {
					theater[tId].seat[i][j] = mId;
				}
			}
		}
		return true;
	}
	return false;
}
Result reserveSeats(int mId, int k) 
{
	Result res;
	for(int t=1; t<=100; t++) {
		if(theater[t].slot >= k) {
			memset(visit, 0, sizeof(visit));
			for(int i = 1; i <= 100; i++) {
				for(int j = 1; j <= 100; j++) {
					if(!visit[i][j] && theater[t].seat[i][j] == 0 && bfs(t, i, j, k, mId)) {
						theater[t].slot -= k;
						mp[mId] = t;
						res.id = t;
						res.num = map[i][j];
						return res;
					}
				}
			}
		}
	}

	res.id = 0;
	res.num = 0;
	return res;
}
Result cancelReservation (int mID) 
{
	Result res;
	int sum = 0;
	int cnt = 0;
	int tId = mp[mID];
	for(int i=1; i<=100; i++) {
		for(int j=1; j<=100; j++) {
			if(theater[tId].seat[i][j] == mID) {
				sum+=map[i][j];
				cnt++;
				theater[tId].seat[i][j] = 0;
			}
		}
	}
	mp[mID] = 0;
	theater[tId].slot += cnt;
	res.id = tId;
	res.num = sum;
	return res;
}