#include "treasure.h"
#define MAX(A, B) ((A) > (B) ? (A) : (B))
int map[101][101];
void _fill(int y, int x, int h, int w) {
for (int i = y; i <= y + h - 1; i++)
for (int j = x; j <= x + w - 1; j++)
map[i][j] = 1;
}
int dfs(int y, int x, int h, int w) {
int cnt = countTreasure(y, x, y+h-1, x+w-1);
if (cnt == 0)
return cnt;
if (cnt == h*w) {
_fill(y, x, h, w);
return cnt;
}
int ys[4], xs[4], hs[4], ws[4], areas[4];
ys[0] = y;
ys[1] = y;
ys[2] = y + h / 2;
ys[3] = y + h / 2;
xs[0] = x;
xs[1] = x + w / 2;
xs[2] = x;
xs[3] = x + w / 2;
hs[0] = MAX(1, h / 2);
hs[1] = MAX(1, h / 2);
hs[2] = h / 2 + (h & 1 ? 1 : 0);
hs[3] = h / 2 + (h & 1 ? 1 : 0);
ws[0] = MAX(1, w / 2);
ws[1] = MAX(1, w / 2 + (w & 1 ? 1 : 0));
ws[2] = w / 2;
ws[3] = w / 2 + (w & 1 ? 1 : 0);
areas[0] = h*w - hs[0] * ws[0];
areas[1] = areas[0] - hs[1] * ws[1];
areas[2] = areas[1] - hs[2] * ws[2];
areas[3] = areas[2] - hs[3] * ws[3];
int s = 0, t;
for (int i = 0; i < 4; i++) {
if (h == 1 && i >= 2)
continue;
if (w == 1 && (i == 1 || i == 3))
continue;
t = dfs(ys[i], xs[i], hs[i], ws[i]);
s += t;
if (s == cnt)
return cnt;
if (cnt-s == areas[i]) {
for (int j = i+1; j < 4; j++) {
if (h == 1 && j >= 2)
continue;
if (w == 1 && (j == 1 || j == 3))
continue;
_fill(ys[j], xs[j], hs[j], ws[j]);
}
return cnt;
}
}
return cnt;
}
void findTreasure (int N) {
dfs (1, 1, N, N);
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
if (map[i][j])
Report(i, j);
}
