Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
5.0 kB
4
Indexable
Never
#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;
 }