#include "treasure.h"
#define MAX 101
int cache[MAX][MAX]; // 해당 좌표 treasure 유무
int log[4][MAX][MAX]; // 기준 좌표에서 해당 좌표까지 treasurer 개수
int size;
int myCountTreasure(int side, int i, int j) {
int &ret = log[side - 1][i][j];
if (ret == -1) {
if (side == 1) { // 1사분면
return ret = countTreasure(i, j, size, size);
}
else if (side == 2) { // 2사분면
return ret = countTreasure(i, 1, size, j);
}
else if (side == 3) { // 3사분면
return ret = countTreasure(1, j, i, size);
}
else { // 4사분면
return ret = countTreasure(1, 1, i, j);
}
}
else
return ret;
}
void side1dp() {
for (int i = size / 2 - 1; i > 0; i--)
cache[i][size / 2 - 1] = myCountTreasure(1, i, size / 2 - 1) - myCountTreasure(1, i + 1, size / 2 - 1) - myCountTreasure(1, i, size / 2) + myCountTreasure(1, i + 1, size / 2);
for (int j = size / 2 - 1; j > 0; j--)
cache[size / 2 - 1][j] = myCountTreasure(1, size / 2 - 1, j) - myCountTreasure(1, size / 2 - 1, j + 1) - myCountTreasure(1, size / 2, j) + myCountTreasure(1, size / 2, j + 1);
for (int i = size / 2 - 2; i > 0; i--) {
for (int j = size / 2 - 2; j > 0; j--) {
cache[i][j] = myCountTreasure(1, i, j) - log[0][i + 1][j] - log[0][i][j + 1] + log[0][i + 1][j + 1];
}
}
}
void side2dp() {
for (int i = size / 2 - 1; i > 0; i--)
cache[i][size / 2] = myCountTreasure(2, i, size / 2) - myCountTreasure(2, i + 1, size / 2) - myCountTreasure(2, i, size / 2 - 1) + myCountTreasure(2, i + 1, size / 2 - 1);
for (int j = size / 2; j <= size; j++)
cache[size / 2 - 1][j] = myCountTreasure(2, size / 2 - 1, j) - myCountTreasure(2, size / 2 - 1, j - 1) - myCountTreasure(2, size / 2, j) + myCountTreasure(2, size / 2, j - 1);
for (int i = size / 2 - 2; i > 0; i--) {
for (int j = size / 2 + 1; j <= size; j++) {
cache[i][j] = myCountTreasure(2, i, j) - log[1][i + 1][j] - log[1][i][j - 1] + log[1][i + 1][j - 1];
}
}
}
void side3dp() {
for (int i = size / 2; i <= size; i++)
cache[i][size / 2 - 1] = myCountTreasure(3, i, size / 2 - 1) - myCountTreasure(3, i - 1, size / 2 - 1) - myCountTreasure(3, i, size / 2) + myCountTreasure(3, i - 1, size / 2);
for (int j = size / 2 - 1; j > 0; j--)
cache[size / 2][j] = myCountTreasure(3, size / 2, j) - myCountTreasure(3, size / 2, j + 1) - myCountTreasure(3, size / 2 - 1, j) + myCountTreasure(3, size / 2 - 1, j + 1);
for (int i = size / 2 + 1; i <= size; i++) {
for (int j = size / 2 - 2; j > 0; j--) {
cache[i][j] = myCountTreasure(3, i, j) - log[2][i - 1][j] - log[2][i][j + 1] + log[2][i - 1][j + 1];
}
}
}
void side4dp() {
for (int i = size / 2; i <= size; i++)
cache[i][size / 2] = myCountTreasure(4, i, size / 2) - myCountTreasure(4, i - 1, size / 2) - myCountTreasure(4, i, size / 2 - 1) + myCountTreasure(4, i - 1, size / 2 - 1);
for (int j = size / 2; j <= size; j++)
cache[size / 2][j] = myCountTreasure(4, size / 2, j) - myCountTreasure(4, size / 2, j - 1) - myCountTreasure(4, size / 2 - 1, j) + myCountTreasure(4, size / 2 - 1, j - 1);
for (int i = size / 2 + 1; i <= size; i++) {
for (int j = size / 2 + 1; j <= size; j++) {
cache[i][j] = myCountTreasure(4, i, j) - myCountTreasure(4, i - 1, j) - myCountTreasure(4, i, j - 1) + myCountTreasure(4, i - 1, j - 1);
}
}
}
void dp() {
if (size > 1) {
cache[1][1] = myCountTreasure(4, size, size) - countTreasure(1, 2, size, size) - countTreasure(2, 1, size, size) + countTreasure(2, 2, size, size);
log[3][1][1] = cache[1][1];
}
else {
cache[1][1] = countTreasure(1, 1, 1, 1);
return;
}
for (int i = 2; i <= size; i++)
cache[i][1] = myCountTreasure(4, i, 1) - log[3][i - 1][1];
for (int j = 2; j <= size; j++)
cache[1][j] = myCountTreasure(4, 1, j) - log[3][1][j - 1];
for (int i = 2; i <= size; i++) {
for (int j = 2; j <= size; j++) {
cache[i][j] = myCountTreasure(4, i, j) - log[3][i - 1][j] - log[3][i][j - 1] + log[3][i - 1][j - 1];
}
}
}
void findTreasure (int N) {
// Initialize
size = N;
for (int i = 1; i <= size; i++)
for (int j = 1; j <= size; j++) {
for (int s = 0; s < 4; s++)
log[s][i][j] = -1;
}
if (size > 10) {
side1dp();
side2dp();
side3dp();
side4dp();
}
else {
dp();
}
for (int i = 1; i <= size; i++)
for (int j = 1; j <= size; j++)
if (cache[i][j])
Report(i, j);
return;
}
