#include "treasure.h"
int Tcnt = 0;
int Treasure[10005][2];
bool visited[105][105];
void search(int r1, int c1, int r2, int c2)
{
if (r1 == r2 && c1 == c2 ) {
if (visited[r1][c1])
return;
Treasure[Tcnt][0] = r1;
Treasure[Tcnt][1] = c1;
Tcnt++;
visited[r1][c1] = true;
return;
}
else
{
int rmid = (r1 + r2) / 2;
int cmid = (c1 + c2) / 2;
if (r1 == r2) {
if(countTreasure(r1, c1, r2, cmid))
search(r1, c1, r2, cmid);
if (countTreasure(r1, cmid + 1, r2, c2))
search(r1, cmid + 1, r2, c2);
return;
}
else if (c1 == c2)
{
if (countTreasure(r1, c1, rmid, c2))
search(r1, c1, rmid, c2);
if (countTreasure(rmid + 1, c1, r2, c2))
search(rmid + 1, c1, r2, c2);
return;
}
else {
if (countTreasure(r1, c1, rmid, cmid))
search(r1, c1, rmid, cmid);
if (countTreasure(r1, cmid + 1, rmid, c2))
search(r1, cmid + 1, rmid, c2);
if (countTreasure(rmid, c1, r2, cmid))
search(rmid, c1, r2, cmid);
if (countTreasure(rmid + 1, cmid + 1, r2, c2))
search(rmid + 1, cmid + 1, r2, c2);
}
}
}
void findTreasure(int N) {
// int cnt = countTreasure(1, 1, N, N);
// if (cnt > 0) Report(1, 1);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
visited[i][j] = false;
}
}
search(1, 1, N, N);
for (int i = 0; i < Tcnt; i++) {
Report(Treasure[i][0], Treasure[i][1]);
}
}
