Untitled
unknown
plain_text
5 months ago
4.0 kB
4
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