#include "worldmap.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
vector<int> edges[45];
int d[45], h[45], subSz[45];
bool perfect[45];
struct RectBoard
{
RectBoard(int c, int a, int b) : color(c), width(a), height(b), depth(0), coverC(0), special(false) {}
int color;
int width, height;
int depth;
int coverC = 0;
bool special;
void add_child(int x, int y, RectBoard* r)
{
childs.emplace_back(ii(x, y), r);
depth = max(depth, r->depth + 1);
if (childs.size() == 1)
coverC = childs[0].yy->coverC + 1;
}
vector<pair<ii, RectBoard*>> childs;
void paint(vector<vector<int>>& res, int x, int y)
{
for (int i = x; i < x + width; i++)
for (int j = y; j < y + height; j++)
res[i][j] = color;
for (auto& [p, c] : childs)
c->paint(res, x + p.xx, y + p.yy);
}
int cover()
{
// cover 필요 없는 경우
if (childs.empty())
return 0;
if (childs[0].xx.xx != 0 && childs[0].xx.yy != 0)
return 0;
auto csz = childs[0].yy->cover() + 1;
childs[0].xx.xx += 1;
childs[0].xx.yy += 1;
width += csz;
height += csz;
for (int i = 1; i < childs.size(); i++)
{
childs[i].xx.xx += csz;
childs[i].xx.yy += csz;
}
compress(1, 1);
return csz;
}
void compress(int sx, int sy)
{
// 특수 모양 제외
if (special)
return;
// 1x1 인 사각형들 전부 분리, 1x1 이상 위치를 기준으로 최대한 껴넣을 수 있는 곳에 껴넣게 변경
vector<RectBoard*> cells;
vector<pair<ii, RectBoard*>> nchilds;
for (auto& [p, c] : childs)
{
if (c->width == 1 && c->height == 1)
cells.push_back(c);
else
nchilds.emplace_back(p, c);
}
childs = nchilds;
vector<ii> targets;
for (int x = sx; x < width - 1;x++)
{
for (int y = sy; y < height - 1;y++)
{
targets.emplace_back(x, y);
}
}
sort(all(targets), [](ii l, ii r) { return max(l.xx, l.yy) < max(r.xx, r.yy); });
for (auto& c : cells)
{
for (auto& [x, y] : targets)
{
bool ok = true;
for (auto& [p, ch] : childs)
{
int lx = p.xx;
int rx = p.xx + ch->width - 1;
int ly = p.yy;
int ry = p.yy + ch->height - 1;
if (x >= lx && x <= rx && y >= ly && y <= ry)
{
ok = false;
break;
}
lx--;
rx++;
ly--;
ry++;
// 영역에 포함은 아니지만 인접
if (x >= lx && x <= rx && y >= ly && y <= ry)
{
if (x == lx && y == ly)
continue;
if (x == lx && y == ry)
continue;
if (x == rx && y == ly)
continue;
if (x == rx && y == ry)
continue;
// 한 칸 여유는 두기
if (c->width > c->height)
{
if (x == rx)
{
ok = false;
break;
}
}
else
{
if (y == ry)
{
ok = false;
break;
}
}
// 인접하지만 색상 조건에 문제없는 경우
if (any_of(all(edges[ch->color]), [x = c->color](int v) { return v == x;}))
continue;
ok = false;
break;
}
}
if (ok)
{
add_child(x, y, c);
break;
}
}
}
width = 0;
height = 0;
for (auto& [p, c] : childs)
{
width = max(width, p.xx + c->width + 1);
height = max(height, p.yy + c->height + 1);
}
}
bool isAdj(ii p)
{
for (auto& [cp, v] : childs)
{
int lx = cp.xx - 1;
int rx = cp.xx + v->width;
int ly = cp.yy - 1;
int ry = cp.yy + v->height;
if (p.xx == lx && p.yy == ly)
continue;
if (p.xx == lx && p.yy == ry)
continue;
if (p.xx == rx && p.yy == ly)
continue;
if (p.xx >= lx && p.xx <= rx && p.yy >= ly && p.yy <= ry)
return true;
}
return false;
}
vector<ii> getCells()
{
vector<ii> res1;
for (int y = 0; y < height - 1; y++)
{
for (int x = y % 2; x < width - 1; x += 2)
{
if (isAdj(ii(x, y)))
continue;
res1.emplace_back(x, y);
}
}
vector<ii> res2;
for (int y = 0; y < height - 1; y++)
{
for (int x = (y + 1) % 2; x < width - 1; x += 2)
{
if (isAdj(ii(x, y)))
continue;
res2.emplace_back(x, y);
}
}
if (res1.size() >= res2.size())
return res1;
else
return res2;
}
void transpose()
{
swap(width, height);
for (auto& [p, c] : childs)
{
swap(p.xx, p.yy);
c->transpose();
}
}
bool overlap(int lx, int ly, int rx, int ry)
{
for (auto& [p, c] : childs)
{
int lx2 = p.xx - 1;
int ly2 = p.yy - 1;
int rx2 = p.xx + c->width;
int ry2 = p.yy + c->height;
int minx = max(lx, lx2);
int maxx = min(rx, rx2);
int miny = max(ly, ly2);
int maxy = min(ry, ry2);
if (minx <= maxx && miny <= maxy)
return true;
}
return false;
}
};
void predfs(int root)
{
subSz[root] = 1;
int backEdge = 0;
vector<int> cs;
for (auto& c : edges[root])
{
if (d[c] != -1)
{
if (d[c] > d[root])
backEdge++;
continue;
}
cs.push_back(c);
d[c] = d[root] + 1;
predfs(c);
h[root] = max(h[root], h[c] + 1);
subSz[root] += subSz[c];
}
if (cs.empty())
{
perfect[root] = true;
}
else if (cs.size() == 1 && perfect[cs[0]] && backEdge == subSz[root] - 2)
{
perfect[root] = true;
}
}
RectBoard* dfs(int root, bool maxFirst)
{
vector<int> backEdges;
vector<RectBoard*> childBoards;
if (maxFirst)
sort(all(edges[root]), [](int l, int r) { return h[r] < h[l]; });
else
sort(all(edges[root]), [](int l, int r) { return h[l] < h[r]; });
int bc = 0;
for (auto& c : edges[root])
{
if (d[c] < d[root])
continue;
// back edge 여부 체크
if (d[c] != d[root] + 1)
{
backEdges.push_back(c);
bc++;
}
else
{
auto dfsr = dfs(c, maxFirst);
if (dfsr->width == 1 && dfsr->height == 1)
{
backEdges.push_back(dfsr->color);
delete dfsr;
}
else
{
childBoards.push_back(dfsr);
}
maxFirst = false;
}
}
// leaf node
if (childBoards.empty() && backEdges.empty())
return new RectBoard(root, 1, 1);
// n = 3 완전 그래프 특수 케이스
if (subSz[root] == 3 && perfect[root])
{
auto res = new RectBoard(root, 2, 3);
res->add_child(0, 0, new RectBoard(childBoards[0]->color, 1, 1));
res->add_child(0, 1, new RectBoard(childBoards[0]->childs[0].yy->color, 1, 1));
res->special = true;
return res;
}
// n = 4 완전 그래프 특수 케이스
if (subSz[root] == 4 && perfect[root])
{
auto res = new RectBoard(root, 3, 4);
res->add_child(0, 0, childBoards[0]);
res->childs[0].yy->add_child(1, 1, new RectBoard(root, 1, 1));
res->childs[0].yy->add_child(1, 2, new RectBoard(res->childs[0].yy->childs[0].yy->color, 1, 1));
res->special = true;
return res;
}
for (int i = 1; i < childBoards.size(); i++)
{
// 왼쪽 위 감싸기
childBoards[i]->cover();
}
// 자식을 한 칸씩 띄고 배치할 수 있을 만큼으로 크기 지정
int width = 0;
int height = 0;
auto res = new RectBoard(root, width, height);
for (auto& c : childBoards)
{
// width를 확장할지 height를 확장할지 정하기
vector<tuple<int, int, bool>> candidates;
for (int x = 0; x <= width; x++)
{
for (int y = 0; y <= height; y++)
{
if (!res->overlap(x, y, x + c->width - 1, y + c->height - 1))
candidates.emplace_back(x, y, false);
if (!res->overlap(x - 1, y - 1, x + c->height, y + c->width))
candidates.emplace_back(x, y, true);
}
}
int x = 0;
int y = 0;
bool needTranspose = false;
int sz = 987654321;
for (auto& [xi, yi, transpose] : candidates)
{
auto wi = transpose ? c->height : c->width;
auto hi = transpose ? c->width : c->height;
auto afterw = max(width, xi + wi + 1);
auto afterh = max(height, yi + hi + 1);
auto aftersz = max(afterw, afterh);
if (aftersz < sz)
{
sz = aftersz;
x = xi;
y = yi;
needTranspose = transpose;
}
}
if (needTranspose)
c->transpose();
res->add_child(x, y, c);
width = max(width, x + c->width + 1);
height = max(height, y + c->height + 1);
}
res->width = width;
res->height = height;
// back edge 칸 계산
if (!backEdges.empty())
{
while (true)
{
vector<ii> cells = res->getCells();
if (cells.size() < backEdges.size())
{
if (res->width < res->height)
res->width += 2;
else
res->height += 2;
continue;
}
for (int i = 0; i < backEdges.size(); i++)
res->add_child(cells[i].xx, cells[i].yy, new RectBoard(backEdges[i], 1, 1));
break;
}
}
return res;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
for (int i = 1; i <= N; i++)
edges[i].clear();
memset(d, -1, sizeof(d));
memset(h, 0, sizeof(h));
memset(subSz, 0, sizeof(subSz));
memset(perfect, false, sizeof(perfect));
for (int i = 0; i < M; i++)
{
edges[A[i]].push_back(B[i]);
edges[B[i]].push_back(A[i]);
}
d[1] = 0;
predfs(1);
auto res = dfs(1, true);
auto sz = max(res->width, res->height);
res->width = sz;
res->height = sz;
vector<vector<int>> ans(sz, vector<int>(sz));
res->paint(ans, 0, 0);
return ans;
}
