#include "treasure.h"
int tmap[101][101]; //-1 : unknown 0 : no treasure 1: treasure
int dir[2][4] = { {0,0,-1,1}, {1, -1, 0,0} };
int myN;
int totaltreasure;
void ecofind(int x1, int y1, int x2, int y2) {
if (totaltreasure == 0) return;
if (x1 == x2 && y1 == y2) {
for (int i = 0; i < 4; i++) {
int nx = x1 + dir[0][i];
int ny = y1 + dir[1][i];
if (nx >= 1 && nx <= myN && ny >= 1 && ny <= myN) {
if (tmap[nx][ny] == 1) {
int a, b, c, d;
if (x1 < nx) { a = x1, c = nx; }
else { a = nx, c = x1; }
if (y1 < ny) { b = y1, d = ny; }
else { b = ny, d = y1; }
tmap[x1][y1] = countTreasure(a, b, c, d) - 1;
if (tmap[x1][x2] == 1) --totaltreasure;
return;
}
}
}
tmap[x1][y1] = countTreasure(x1, y1, x2, y2);
if (tmap[x1][x2] == 1) --totaltreasure;
return;
}
int cnt = countTreasure(x1, y1, x2, y2);
if (cnt == 0) return;
if (cnt == (x2 - x1 + 1)*(y2 - y1 + 1)) {
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) tmap[i][j] = 1;
}
totaltreasure -= (x2 - x1 + 1)*(y2 - y1 + 1);
}
else {
int mid = (x1 + x2) / 2;
ecofind(x1, y1, mid, mid);
ecofind(mid + 1, y1, x2, mid);
ecofind(x1, mid + 1, mid, y2);
ecofind(mid + 1, mid + 1, x2, y2);
}
}
void findTreasure(int N) {
for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) tmap[i][j] = -1;
myN = N;
totaltreasure = countTreasure(1, 1, N, N);
if (totaltreasure == 0) return;
if (N == 1) {
if (countTreasure(1, 1, 1, 1) == 1) Report(1, 1);
return;
}
if (N % 2 == 0) {
int mid = (1 + N) / 2;
ecofind(1, 1, mid, mid);
ecofind(mid + 1, 1, N, mid);
ecofind(1, mid + 1, mid, N);
ecofind(mid + 1, mid + 1, N, N);
}
else {
int mid = N / 2;
ecofind(1, 1, mid, mid);
ecofind(mid + 1, 1, N-1, mid);
ecofind(1, mid + 1, mid, N - 1);
ecofind(mid + 1, mid + 1, N - 1, N - 1);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (tmap[i][j] == -1) tmap[i][j] = countTreasure(i, j, i, j);
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (tmap[i][j] == 1) Report(i, j);
}
}
}
