#include "treasure.h"
int map[101][101];
void finding(int r1, int c1, int r2, int c2, int size, int remain) {
int cnt = 0;
if (remain == 0) return;
else if (remain == size*size) {
for (int i = r1; i <= r2; i++)
for (int j = c1; j <= c2; j++) {
if (map[i][j]) continue;
map[i][j] = 1;
}
}
if (size == 2) {
int tmp, temp, cnt = 0;
tmp = countTreasure(r1, c1, r1, c1);
if (tmp) {
cnt++;
if (!map[r1][c1]) {
map[r1][c1] = 1;
}
}
if (cnt == remain) return;
temp = countTreasure(r1, c1, r1, c1 + 1);
if (temp - tmp > 0) {
cnt++;
if (!map[r1][c1 + 1]) {
map[r1][c1 + 1] = 1;
}
}
if (cnt == remain) return;
temp = countTreasure(r1, c1, r1 + 1, c1);
if (temp - tmp > 0) {
cnt++;
if (!map[r1 + 1][c1]) {
map[r1 + 1][c1] = 1;
}
}
if (cnt == remain) return;
if (!map[r1 + 1][c1 + 1]) {
map[r1 + 1][c1 + 1] = 1;
}
return;
}
int r = r1, c = c1;
int tmp = countTreasure(r, r + size / 2, c, c + size / 2);
cnt += tmp;
finding(r, r + size / 2, c, c + size / 2, size / 2, remain - tmp);
if (cnt == remain) return;
r = r1, c = c1 + size / 2;
tmp = countTreasure(r, r + size - size / 2, c, c + size - size / 2);
cnt += tmp;
finding(r, r + size - size / 2, c, c + size - size / 2, size - size / 2, remain - tmp);
if (cnt == remain) return;
r = r1 + size / 2, c = c1;
tmp = countTreasure(r, r + size - size / 2, c, c + size - size / 2);
cnt += tmp;
finding(r, r + size - size / 2, c, c + size - size / 2, size - size / 2, remain - tmp);
if (cnt == remain) return;
r = r1 + size - size / 2, c = c1 + size - size / 2;
tmp = countTreasure(r, r + size / 2, c, c + size / 2);
finding(r, r + size / 2, c, c + size / 2, size / 2, remain - tmp);
}
void findTreasure(int N) {
int tmp = countTreasure(1, 1, N, N);
finding(1, 1, N, N, N, tmp);
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
if (map[i][j]) Report(i, j);
}
