Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
6.8 kB
2
Indexable
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