Untitled
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; }