#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);
}
return ret;
}
void func(Pos pos) {
if(dp[pos.r][pos.c][pos.r][pos.c]!=-1)
vec.push_back(pos);
else {
if (pos.r < halfLimit) {
// left up
if (pos.c < halfLimit) {
int bigBox = isDpValue(pos.r, pos.c, limit, limit); // 1,1,2,2
int underBox = isDpValue(pos.r + 1, pos.c, limit, limit); // 2,1,2,2
int rightBox = isDpValue(pos.r, pos.c + 1, limit, limit); // 1,2,2,2
int commonBox = isDpValue(pos.r + 1, pos.c + 1, limit, limit); // 2,2
if (bigBox - underBox - rightBox + commonBox > 0)
vec.push_back(pos);
}
// right up
else {
int bigBox = isDpValue(pos.r, 1, limit, pos.c);
int underBox = isDpValue(pos.r + 1, 1, limit, pos.c);
int leftBox = isDpValue(pos.r, 1, limit, pos.c - 1);
int commonBox = isDpValue(pos.r + 1, 1, limit, pos.c - 1);
if (bigBox - underBox - leftBox + commonBox > 0)
vec.push_back(pos);
}
}
//left down
else if (pos.c < halfLimit) {
int bigBox = isDpValue(1, pos.c, pos.r, limit);
int upperBox = isDpValue(1, pos.c, pos.r - 1, limit);
int rightBox = isDpValue(1, pos.c + 1, pos.r, limit);
int commonBox = isDpValue(1, pos.c + 1, pos.r - 1, limit);
if (bigBox - upperBox - rightBox + commonBox > 0)
vec.push_back(pos);
}
// right down
else {
int bigBox = isDpValue(1, 1, pos.r, pos.c);
int upperBox = isDpValue(1, 1, pos.r - 1, pos.c);
int leftBox = isDpValue(1, 1, pos.r, pos.c - 1);
int commonBox = isDpValue(1, 1, pos.r - 1, pos.c - 1);
if (bigBox - upperBox - leftBox + commonBox > 0)
vec.push_back(pos);
}
}
}
void findTreasure(int N) {
limit = N;
halfLimit = N / 2 + 1;
memset(dp, -1, sizeof(dp));
Pos pos = { 0,0 };
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
pos.r = i, pos.c = j;
func(pos);
}
}
for (int i = 0; i < vec.size(); i++)
Report(vec[i].r, vec[i].c);
}
