#include "treasure.h"
//#include"header.h"
int result[10009][4];
int rl;
void dfs(int remain, int si, int ei, int sj, int ej) {
if (ei < si)return;
if (ej < sj)return;
if (remain == (ei - si + 1) * (ej - sj + 1)) {
result[rl][0] = si;
result[rl][1] = ei;
result[rl][2] = sj;
result[rl][3] = ej;
rl++;
return;
}
if (remain == 0) {
return;
}
if (si == ei) {
int mj = (sj + ej) / 2;
int ab = countTreasure(si + 1, sj + 1, ei + 1, mj + 1);
dfs(ab, si, ei, sj, mj);
dfs(remain - ab, si, ei, mj + 1, ej);
}
else if (sj == ej) {
int mi = (si + ei) / 2;
int ac = countTreasure(si + 1, sj + 1, mi + 1, ej + 1);
dfs(ac, si, mi, sj, ej);
dfs(remain - ac, mi + 1, ei, sj, ej);
}
else {
int mi = (si + ei) / 2;
int mj = (sj + ej) / 2;
int ab = countTreasure(si + 1, sj + 1, ei + 1, mj + 1);
if (ab == (ei - si + 1) * (mj - sj + 1)) {
dfs(ab, si, ei, sj, mj);
dfs(remain - ab, si, ei, mj + 1, ej);
return;
}
int ac = countTreasure(si + 1, sj + 1, mi + 1, ej + 1);
if (ac == (mi - si + 1) * (ej - sj + 1)) {
dfs(ac, si, mi, sj, ej);
dfs(remain - ac, mi + 1, ei, sj, ej);
return;
}
int aa = countTreasure(si + 1, sj + 1, mi + 1, mj + 1);
dfs(aa, si, mi, sj, mj);
dfs(ab - aa, mi + 1, ei, sj, mj);
dfs(ac - aa, si, mi, mj + 1, ej);
dfs(remain - ab - ac + aa, mi + 1, ei, mj + 1, ej);
}
}
void findTreasure(int N) {
int cnt = countTreasure(1, 1, N, N);
if (cnt == 0)return;
else {
rl = 0;
dfs(cnt, 0, N - 1, 0, N - 1);
while (rl--) {
for (int i = result[rl][0]; i <= result[rl][1]; i++) {
for (int j = result[rl][2]; j <= result[rl][3]; j++) {
Report(i + 1, j + 1);
}
}
}
}
}
