#include "treasure.h"
int map[101][101], sum[4][101][101];
int mycount(int r1, int c1, int r2, int c2, int mode) {
int row = r2 - r1+1, col = c2 - c1+1;
if (!mode) {
if (sum[mode][r2][c2]) return sum[mode][r2][c2];
sum[mode][r2][c2] = countTreasure(r1, c1, r2, c2);
if (sum[mode][r2][c2] == row*col) {
for (int i = r1; i <= r2; i++)
for (int j = c1; j <= c2; j++)
map[i][j] = 1;
}
return sum[mode][r2][c2];
}
else if (mode == 1) {
if (sum[mode][r1][c1]) return sum[mode][r1][c1];
sum[mode][r1][c1] = countTreasure(r1, c1, r2, c2);
if (sum[mode][r1][c1] == row*col) {
for (int i = r1; i <= r2; i++)
for (int j = c1; j <= c2; j++)
map[i][j] = 1;
}
return sum[mode][r1][c1];
}
else if (mode == 2) {
if (sum[mode][r1][c2]) return sum[mode][r1][c2];
sum[mode][r1][c2] = countTreasure(r1, c1, r2, c2);
if (sum[mode][r1][c2] == row*col) {
for (int i = r1; i <= r2; i++)
for (int j = c1; j <= c2; j++)
map[i][j] = 1;
}
return sum[mode][r1][c2];
}
else {
if (sum[mode][r2][c1]) return sum[mode][r2][c1];
sum[mode][r2][c1] = countTreasure(r1, c1, r2, c2);
if (sum[mode][r2][c1] == row*col) {
for (int i = r1; i <= r2; i++)
for (int j = c1; j <= c2; j++)
map[i][j] = 1;
}
return sum[mode][r2][c1];
}
}
void findTreasure(int N) {
for (int i = N; i > N/2; i--)
for (int j = N; j > N / 2; j--) {
if (!map[i][j]) map[i][j] = mycount(1, 1, i, j, 0) - mycount(1, 1, i - 1, j, 0) - mycount(1, 1, i, j - 1, 0) + mycount(1, 1, i - 1, j - 1, 0);
}
for (int i = 1; i <= N / 2; i++)
for (int j = 1; j <= N / 2; j++)
if (!map[i][j]) map[i][j] = mycount(i, j, N, N, 1) - mycount(i, j + 1, N, N, 1) - mycount(i + 1, j, N, N, 1) + mycount(i + 1, j + 1, N, N, 1);
for (int i = 1; i <= N / 2; i++)
for (int j = N; j > N / 2; j--)
if (!map[i][j]) map[i][j] = mycount(i, 1, N, j, 2) - mycount(i, 1, N, j - 1, 2) - mycount(i + 1, 1, N, j, 2) + mycount(i + 1, 1, N, j - 1, 2);
for (int i = N; i > N / 2; i--)
for (int j = 1; j <= N / 2; j++)
if (!map[i][j]) map[i][j] = mycount(1, j, i, N, 3) - mycount(1, j + 1, i, N, 3) - mycount(1, j, i - 1, N, 3) + mycount(1, j + 1, i - 1, N, 3);
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
if (map[i][j]) Report(i, j);
}
