#include "treasure.h"
#include <iostream>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[101][101][101][101];
struct Pos {
int r, c;
};
int limit = 0;
int halfLimit = 0;
vector<Pos> vec;
int isDpValue(int r1, int c1, int r2, int c2) {
int& ret = dp[r1][c1][r2][c2];
if (ret == -1) {
ret = countTreasure(r1, c1, r2, c2);
}
if (ret == 0) {
for (int i = r1; i <= r2; i++) {
for (int j = c1; j <= c2; j++) {
for (int k = i; k <= r2; k++) {
for (int p = j; p <= c2; p++) {
dp[i][j][k][p] = 0;
}
}
}
}
}
return ret;
}
int caseFunc(Pos start, Pos end) {
int bigBox, underBox, upperBox, leftBox, rightBox, commonBox;
if (dp[start.r][start.c][start.r][start.c] == 1)
return 1;
else {
if (start.r <= halfLimit) {
// left up
if (start.c < halfLimit) {
bigBox = isDpValue(start.r, start.c, limit, limit); // 1,1,2,2
if (bigBox == 0) return 0;
underBox = isDpValue(end.r + 1, start.c, limit, limit); // 2,1,2,2
rightBox = isDpValue(start.r, end.c + 1, limit, limit); // 1,2,2,2
if (underBox*rightBox == 0) commonBox = 0;
else
commonBox = isDpValue(end.r + 1, end.c + 1, limit, limit); // 2,2
return bigBox - underBox - rightBox + commonBox;
}
// right up
else {
bigBox = isDpValue(start.r, 1, limit, end.c);
if (bigBox == 0) return 0;
underBox = isDpValue(end.r + 1, 1, limit, end.c);
leftBox = isDpValue(start.r, 1, limit, start.c - 1);
if (underBox *leftBox == 0) commonBox = 0;
else
commonBox = isDpValue(end.r + 1, 1, limit, start.c - 1);
return bigBox - underBox - leftBox + commonBox;
}
}
//left down
else if (start.c <= halfLimit) {
bigBox = isDpValue(1, start.c, end.r, limit);
if (bigBox == 0) return 0;
upperBox = isDpValue(1, start.c, start.r - 1, limit);
rightBox = isDpValue(1, end.c + 1, end.r, limit);
if (upperBox *rightBox == 0) commonBox = 0;
else
commonBox = isDpValue(1, end.c + 1, start.r-1, limit);
return bigBox - upperBox - rightBox + commonBox;
}
// right down
else {
bigBox = isDpValue(1, 1, end.r, end.c);
if (bigBox == 0) return 0;
upperBox = isDpValue(1, 1, start.r - 1, end.c);
leftBox = isDpValue(1, 1, end.r, start.c - 1);
if (upperBox*leftBox == 0) commonBox = 0;
else commonBox = isDpValue(1, 1, start.r - 1, start.c - 1);
return bigBox - upperBox - leftBox + commonBox;
}
}
}
int divide(int num) {
return num % 2 == 1 ? num / 2 : num / 2 + 1;
}
int devideFunc(int r1, int c1, int r2, int c2, int val) {
Pos p, q;
p.r = r1, p.c = c1;
q.r = r2; q.c = c2;
int ret = 0;
if (val != -1)
ret = val;
else ret = caseFunc(p, q);
if ((r2 - r1 + 1)*(c2 - c1 + 1) == ret)
for (int i = r1; i <= r2; i++) {
for (int j = c1; j <= c2; j++) {
p.r = i, p.c = j;
vec.push_back(p);
}
}
else if (ret != 0) {
int a = devideFunc(r1, c1, divide(r2), divide(c2), -1);
int b = devideFunc(r1, divide(c2) + 1, divide(r2), c2, -1);
int c = devideFunc(divide(r2) + 1, c1, r2, divide(c2), -1);
int d = ret - a - b - c;
devideFunc(r2 / 2 + 1, c2 / 2 + 1, r2, c2, d);
}
return ret;
}
void findTreasure(int N) {
limit = N;
if (N & 1)
halfLimit = N / 2;
else
halfLimit = N / 2 + 1;
memset(dp, -1, sizeof(dp));
int ct = countTreasure(1, 1, N, N);
devideFunc(1, 1, N, N,ct );
for (int i = 0; i < vec.size(); i++)
Report(vec[i].r, vec[i].c);
}
