Untitled

 avatar
unknown
plain_text
5 months ago
4.0 kB
2
Indexable
import java.util.*;

public class BlockExtraction {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int rows = sc.nextInt();
        int cols = sc.nextInt();
        int[][] grid = new int[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grid[i][j] = sc.nextInt();
            }
        }

        int target = sc.nextInt();

        Map<Integer, List<int[]>> blockPositions = new HashMap<>();
        Set<Integer> blockTypes = new HashSet<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int block = grid[i][j];
                blockPositions.computeIfAbsent(block, k -> new ArrayList<>()).add(new int[]{i, j});
                blockTypes.add(block);
            }
        }

        Set<Integer> blocksToRemove = new HashSet<>();
        for (int i = 0; i < rows; i++) {
            List<Integer> targetCols = new ArrayList<>();
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == target) {
                    targetCols.add(j);
                }
            }
            if (!targetCols.isEmpty()) {
                int rightmostCol = Collections.max(targetCols);
                for (int j = rightmostCol + 1; j < cols; j++) {
                    int blockType = grid[i][j];
                    if (blockType != target) {
                        blocksToRemove.add(blockType);
                    }
                }
            }
        }

        Set<Integer> remainingBlocks = new HashSet<>(blockTypes);
        blocksToRemove.remove(target);
        int removedBlocks = 0;
        for (int block : blocksToRemove) {
            if (remainingBlocks.contains(block)) {
                remainingBlocks.remove(block);
                removedBlocks++;
            }
        }

        while (true) {
            Set<Integer> supportedBlocks = findSupportedBlocks(remainingBlocks, blockPositions, grid, rows);
            Set<Integer> blocksToRemoveNext = new HashSet<>();
            for (int block : remainingBlocks) {
                if (!supportedBlocks.contains(block)) {
                    blocksToRemoveNext.add(block);
                }
            }
            if (blocksToRemoveNext.isEmpty()) break;
            for (int block : blocksToRemoveNext) {
                remainingBlocks.remove(block);
                removedBlocks++;
            }
        }

        System.out.println(removedBlocks);
    }

    private static Set<Integer> findSupportedBlocks(Set<Integer> blocks, Map<Integer, List<int[]>> blockPositions, int[][] grid, int rows) {
        Set<Integer> supportedBlocks = new HashSet<>();
        for (int block : blocks) {
            for (int[] position : blockPositions.get(block)) {
                if (position[0] == rows - 1) {
                    supportedBlocks.add(block);
                    break;
                }
            }
        }

        Queue<Integer> blocksQueue = new LinkedList<>(supportedBlocks);
        while (!blocksQueue.isEmpty()) {
            int block = blocksQueue.poll();
            for (int b : blocks) {
                if (supportedBlocks.contains(b)) continue;
                boolean isSupported = false;
                for (int[] position : blockPositions.get(b)) {
                    if (position[0] + 1 < rows) {
                        int belowBlock = grid[position[0] + 1][position[1]];
                        if (supportedBlocks.contains(belowBlock)) {
                            isSupported = true;
                            break;
                        }
                    }
                }
                if (isSupported) {
                    supportedBlocks.add(b);
                    blocksQueue.add(b);
                }
            }
        }
        return supportedBlocks;
    }
}
Editor is loading...
Leave a Comment