Untitled
unknown
plain_text
19 days ago
6.8 kB
2
Indexable
Never
import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; import java.util.Queue; class UserSolution { int n; int[][] map, mapCp; int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; HashMap<Integer, ArrayList<Integer>> hash_map_1, hash_map_2; public void init(int N, int mMap[][]) { n = N; mapCp = new int[N][N]; map = mMap; hash_map_1 = new HashMap<Integer, ArrayList<Integer>>(); hash_map_2 = new HashMap<Integer, ArrayList<Integer>>(); for(int i = 0; i < N; i ++){ for(int j = 0; j < N; j++){ mapCp[i][j] = mMap[i][j]; for(int k = 2; k <= 5; k++){ if(j + k > N) break; int sum = 0, sum_r = 0, sum1 = 0, sum1_r = 0; for(int l = j + 1; l < k + j; l++){ sum = sum * 10 + mMap[i][l] - mMap[i][j] + 5; sum_r = sum_r * 10 + mMap[i][k + 2 * j - l - 1] - mMap[i][k + j - 1] + 5; sum1 = sum1 * 10 + mMap[l][i] - mMap[j][i] + 5; sum1_r = sum1_r * 10 + mMap[k + 2 * j - l - 1][i] - mMap[k + j - 1][i] + 5; } if(!hash_map_1.containsKey(sum)){ hash_map_1.put(sum, new ArrayList<Integer>()); } hash_map_1.get(sum).add(i * N + j); if(!hash_map_1.containsKey(sum_r)){ hash_map_1.put(sum_r, new ArrayList<Integer>()); } if(sum != sum_r) hash_map_1.get(sum_r).add(i * N + j); if(!hash_map_2.containsKey(sum1)){ hash_map_2.put(sum1, new ArrayList<Integer>()); } hash_map_2.get(sum1).add(j * N + i); if(!hash_map_2.containsKey(sum1_r)) hash_map_2.put(sum1_r, new ArrayList<Integer>()); if(sum1 != sum1_r) hash_map_2.get(sum1_r).add(j * N + i); } } } } public int numberOfCandidate(int M, int mStructure[]) { int sum = 0, count = 0; if(M == 1) return n * n; for(int i = 1; i < M; i++){ sum = sum * 10 + mStructure[0] - mStructure[i] + 5; } if(hash_map_1.containsKey(sum)){ count += hash_map_1.get(sum).size(); } if(hash_map_2.containsKey(sum)){ count += hash_map_2.get(sum).size(); } return count; } public int maxArea(int M, int mStructure[], int mSeaLevel) { int sum = 0; int mMax = -1; for(int i = 1; i < M; i++){ sum = sum * 10 + mStructure[0] - mStructure[i] + 5; } if(M == 1){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ map[i][j] += mStructure[0]; int countPlace = bfs(mSeaLevel); if(mMax < countPlace){ mMax = countPlace; } map[i][j] -= mStructure[0]; } } return mMax; } if(hash_map_1.containsKey(sum)){ for(int pos : hash_map_1.get(sum)){ int y = pos / n; int x = pos % n; int index = check_1(x, y, M, mStructure); int height = map[y][x] + mStructure[index]; for(int i = 0; i < M; i++){ map[y][x + i] = height; } int countPlace = bfs(mSeaLevel); if(mMax < countPlace){ mMax = countPlace; } for(int i = 0; i < M; i++){ map[y][x + i] = mapCp[y][x + i]; } } } if(hash_map_2.containsKey(sum)){ for(int pos : hash_map_2.get(sum)){ int y = pos / n; int x = pos % n; int index = check_2(x, y, M, mStructure); int height = map[y][x] + mStructure[index]; for(int i = 0; i < M; i++){ map[y + i][x] = height; } int countPlace = bfs(mSeaLevel); if(mMax < countPlace){ mMax = countPlace; } for(int i = 0; i < M; i++){ map[y + i][x] = mapCp[y + i][x]; } } } return mMax; } int check_1(int x, int y, int M, int[] mStructure){ for(int i = 0; i < M - 1; i++){ if(map[y][x + i] + mStructure[i] != map[y][x + i + 1] + mStructure[i + 1]) return M - 1; } return 0; } int check_2(int x, int y, int M, int[] mStructure){ for(int i = 0; i < M - 1; i++){ if(map[y + i][x] + mStructure[i] != map[y + i + 1][x] + mStructure[i + 1]) return M - 1; } return 0; } int bfs(int mSeaLevel){ Queue<Point> q = new LinkedList<Point>(); int cnt = 0; int[][] visited = new int[n][n]; for(int i = 0; i < n; i ++){ if(map[0][i] < mSeaLevel){ q.add(new Point(i, 0)); visited[0][i] = 1; cnt++; } if(map[n - 1][i] < mSeaLevel){ q.add(new Point(i, n - 1)); visited[n - 1][i] = 1; cnt++; } } for(int i = 1; i < n - 1; i ++){ if(map[i][0] < mSeaLevel){ q.add(new Point(0, i)); visited[i][0] = 1; cnt++; } if(map[i][n - 1] < mSeaLevel){ q.add(new Point(n - 1, i)); visited[i][n - 1] = 1; cnt++; } } while(!q.isEmpty()){ Point c = q.poll(); for(int k = 0; k < 4; k++){ int x = c.x + dx[k]; int y = c.y + dy[k]; if(x >= 0 && x < n && y >= 0 && y < n && visited[y][x] == 0 && map[y][x] < mSeaLevel){ cnt++; visited[y][x] = 1; q.add(new Point(x, y)); } } } return n * n - cnt; } class Point{ int x, y; public Point(int x, int y){ this.x = x; this.y = y; } } }
Leave a Comment