#define MAX 10000
using namespace std;
struct Node {
int r, c, reverse, nextH;
}node[10000];
int hashTB[2][MAX];//0->horizonal, 1->vertical
int mcount[MAX];
int id;//number of node
int map[22][22], N;
int queuex[400], queuey[400], visitCnt = 0;
int f, r;
int visit[22][22];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int largest;
int coso[5] = {0, 1, 10, 100, 1000};
void add(int row, int col, int val, int rev, int type) {
mcount[val]++;
node[id].r = row;
node[id].c = col;
node[id].reverse = rev;
node[id].nextH = hashTB[type][val];
hashTB[type][val] = id++;
}
void init(int n, int mmap[][20]){
N = n;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) map[i][j] = mmap[i][j];
}
id = 1;
for(int i = 0; i < MAX; i++) {
mcount[i] = 0;
hashTB[0][i] = 0;
hashTB[1][i] = 0;
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
int ngang[2] = {0, 0}, doc[2] = {0, 0};
for(int k = 1; k < 5; k++) {
if(j+k < N) {
ngang[0] = ngang[0] * 10 + (map[i][j+k] - map[i][j+k-1] + 5);
add(i, j, ngang[0], 0, 0);
ngang[1] = ngang[1] + (map[i][j+k-1] - map[i][j+k] + 5) * coso[k];
if(ngang[1] != ngang[0]) add(i, j, ngang[1], 1, 0);
}
if(i+k < N) {
doc[0] = doc[0] * 10 + (map[i+k][j] - map[i+k-1][j] + 5);
add(i, j, doc[0], 0, 1);
doc[1] = doc[1] + (map[i+k-1][j] - map[i+k][j] + 5) * coso[k];
if(doc[1] != doc[0]) add(i, j, doc[1], 1, 1);
}
}
}
}
}
int numberOfCandidate(int M, int mstruct[5]){
int val = 0;
if(M == 1) return N * N;
for(int i = 1; i < M; i++) val = val * 10 + (mstruct[i-1] - mstruct[i] + 5);
return mcount[val];
}
void bfs(int mlevel){//sea level
visitCnt++;
int Sum = N * N;
f = 0; r = 0;
for(int i = 0; i < N; i++) {
if(map[i][0] < mlevel) {
Sum--;
visit[i][0] = visitCnt;
queuex[r] = i;
queuey[r] = 0; r++;
}
if(map[i][N-1] < mlevel) {
visit[i][N-1] = visitCnt;
Sum--;
queuex[r] = i;
queuey[r] = N-1; r++;
}
}
for(int j = 1; j < N-1; j++) {
if(map[0][j] < mlevel) {
visit[0][j] = visitCnt;
Sum--;
queuex[r] = 0;
queuey[r] = j; r++;
}
if(map[N-1][j] < mlevel) {
visit[N-1][j] = visitCnt;
Sum--;
queuex[r] = N-1;
queuey[r] = j; r++;
}
}
while (f < r)
{
int x = queuex[f], y = queuey[f];
f++;
for(int i = 0; i < 4; i++) {
int nx = x+ dx[i], ny = y + dy[i];
if(nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] < mlevel && visit[nx][ny] < visitCnt) {
visit[nx][ny] = visitCnt;
queuex[r] = nx;
queuey[r] = ny; r++;
Sum--;
}
}
}
if(largest < Sum) largest = Sum;
}
int maxArea(int M, int mstruct[5], int mlevel) {
largest = -1;
if(M == 1) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
map[i][j] += mstruct[0];
bfs(mlevel);
map[i][j] -= mstruct[0];
}
}
return largest;
}
int val = 0;
for(int i = 1; i < M; i++) val = val * 10 + (mstruct[i-1] - mstruct[i] + 5);
int idp = hashTB[0][val];
while (idp)
{
int row = node[idp].r, col = node[idp].c;
for(int i = 0; i < M; i++) {
if(node[idp].reverse == 0) map[row][col+i] += mstruct[i];
else map[row][col+i] += mstruct[M-1-i];
}
bfs(mlevel);
for(int i = 0; i < M; i++) {
if(node[idp].reverse == 0) map[row][col+i] -= mstruct[i];
else map[row][col+i] -= mstruct[M-1-i];
}
idp = node[idp].nextH;
}
idp = hashTB[1][val];
while (idp)
{
int row = node[idp].r, col = node[idp].c;
for(int i = 0; i < M; i++) {
if(node[idp].reverse == 0) map[row+i][col] += mstruct[i];
else map[row+i][col] += mstruct[M-1-i];
}
bfs(mlevel);
for(int i = 0; i < M; i++) {
if(node[idp].reverse == 0) map[row+i][col] -= mstruct[i];
else map[row+i][col] -= mstruct[M-1-i];
}
idp = node[idp].nextH;
}
return largest;
}