#include "treasure.h"
int n, cnt;
int mat[105][105];
bool vi[105][105];
bool sf(int x, int y) {
return (x >= 1 && y >= 1 && x <= n && y <= n);
}
void find_(int l, int r, int x) {
//printf("%d %d %d\n", x, l, r);
if (cnt == 0)return;
if (!sf(x, l) || !sf(x, r))return;
if (r < 1 || l>n)return;
if (r - l + 1 <= 0)return;
int count_ = countTreasure(x, l, x, r);
if (count_ == 0)return;
if (r - l + 1 == count_) {
for (int i = l; i <= r; i++) {
mat[x][i] = 1;
cnt--;
}
return;
}
if (r - l + 1 == 1) {
return;
}
find_(l, (l + r) / 2, x);
if (cnt == 0)return;
find_((l + r) / 2 + 1, r, x);
return;
}
void find_2(int x,int y,int si) {
//printf("->%d %d %d\n", x, y, si);
if (!sf(x, y))return;
int six = 0;
int siy = 0;
for (int i = x; i < x+si && i<=n; i++)six++;
for (int i = y; i<y+si&&i <= n; i++)siy++;
int count_ = countTreasure(x, y, x + six-1, y + siy - 1);
if (si <= 2 && count_>0) {
cnt = count_;
for(int i=x;i<x+si;i++)
find_(y, y + si-1, i);
return;
}
if (count_ == 0)return;
int ran = 0;
for (int i = x; i <= n && i < x + si; i++)
for (int j = y; j <= n && j < y + si; j++)
ran++;
if (count_ == ran) {
for (int i = x; i <= n && i < x + si; i++)
for (int j = y; j <= n && j < y + si; j++)
mat[i][j] = 1;
return;
}
find_2(x, y, ((si + 1) / 2));
find_2(x+((si + 1) / 2), y, ((si + 1) / 2));
find_2(x, y + ((si + 1) / 2), ((si + 1) / 2));
find_2(x + ((si + 1) / 2), y + ((si + 1) / 2), ((si + 1) / 2));
return;
}
void findTreasure(int N) {
n = N;
for (int i = 1; i <= n; i++)
for (int j = 1; j < n; j++)
mat[i][j] = 0;
//for (int i = 1; i <= N; i++) {
// cnt = countTreasure(i,1,i,n);
// find_(1, n, i);
//}
find_2(1, 1, n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (mat[i][j] == 1)Report(i, j);
//printf("%d", mat[i][j]);
}//printf("\n");
}
}
