#include "treasure.h"
int cnt;
int chk[105][105];
int n;
void search(int r1, int c1, int r2, int c2, int mod)//짝이면 세로로 나눔, 홀이면 가로로 나눔
{
if (mod % 2 == 0)
{
int mid = c1 + (c2 - c1) / 2;
int blocks = (mid - c1+1)*(r2 - r1+1);
if (blocks > 0)
{
int treasures = countTreasure(r1, c1, r2, mid);
if (blocks == treasures)
{
for (int i = r1; i <= r2; i++)
{
for (int j = c1; j <= mid; j++)
chk[i][j] = true;
}
}
else if(treasures!=0)
{
search(r1, c1, r2, mid, mod + 1);
}
}
blocks = (c2 - mid)*(r2 - r1+1);
if (blocks > 0)
{
int treasures = countTreasure(r1, mid + 1, r2, c2);
if (blocks == treasures)
{
for (int i = r1; i <= r2; i++)
{
for (int j = mid + 1; j <= c2; j++)
chk[i][j] = true;
}
}
else if (treasures != 0)
{
search(r1, mid + 1, r2, c2, mod + 1);
}
}
}
else
{
int mid = r1 + (r2 - r1) / 2;
int blocks = (c2 - c1+1)*(mid - r1+1);
if (blocks > 0)
{
int treasures = countTreasure(r1, c1, mid, c2);
if (blocks == treasures)
{
for (int i = r1; i <= mid; i++)
{
for (int j = c1; j <= c2; j++)
chk[i][j] = true;
}
}
else if (treasures != 0)
{
search(r1, c1, mid, c2, mod + 1);
}
}
blocks = (r2 - mid)*(c2 - c1+1);
if (blocks > 0)
{
int treasures = countTreasure(mid + 1, c1, r2, c2);
if (blocks == treasures)
{
for (int i = mid + 1; i <= r2; i++)
{
for (int j = c1; j <= c2; j++)
chk[i][j] = true;
}
}
else if(treasures != 0)
{
search(mid + 1, c1, r2, c2, mod + 1);
}
}
}
}
void init()
{
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
chk[i][j] = false;
}
void findTreasure(int N) {
n = N;
cnt = countTreasure(1, 1, N, N);
init();
search(1, 1, n, n, 0);
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
if (chk[i][j]) Report(i, j);
}
}
