#include "treasure.h"
bool isl[101][101];
int dncTreasure(int r1, int c1, int r2, int c2, int cnt){
if(r2 < r1 || c2 < c1) return 0;
if(cnt == -1) cnt = countTreasure(r1, c1, r2, c2);
if(cnt == 0) return 0;
if(cnt == (r2 - r1 + 1) * (c2 - c1 + 1)){
for(int i = r1; i <= r2; i++)
for(int j = c1; j <= c2; j++)
isl[i][j] = true;
return cnt;
}
int rlen = (r2 - r1), clen = (c2 - c1);
if(rlen >= clen){
rlen /= 2;
int t = dncTreasure(r1, c1, r1 + rlen, c2, -1);
dncTreasure(r1 + rlen + 1, c1, r2, c2, cnt - t);
}
else{
clen /= 2;
int t = dncTreasure(r1, c1, r2, c1 + clen, -1);
dncTreasure(r1, c1 + clen + 1, r2, c2, cnt - t);
}
return cnt;
}
void findTreasure (int N) {
dncTreasure(1, 1, N, N, -1);
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(isl[i][j]){
isl[i][j] = false;
Report(i, j);
}
}
}
}
