Bleeding Ink

bleeding-ink.pdf

BleedingInk.java

package me.soulmachine;

import java.util.*;

public class BleedingInk {
    class State {
        int x;
        int y;
        int parentDarkness;

        State(int x, int y, int parentDarkness) {
            this.x = x;
            this.y = y;
            this.parentDarkness = parentDarkness;
        }
    }

    private int[][] grid;
    private int[][] drops;
    private boolean[][] visited;

    public BleedingInk(int[][] grid, int[][] drops) {
        this.grid = grid;
        this.drops = drops;
        this.visited = new boolean[grid.length][grid[0].length];
    }

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int numCases = scanner.nextInt();
        for (int i = 0; i < numCases; ++i) {
            int h = scanner.nextInt();
            int w = scanner.nextInt();
            int[][] grid = new int[h][w];
            int nums = scanner.nextInt();
            int[][] drops = new int[nums][2];
            for (int j = 0; j < nums; ++j) {
                int y = scanner.nextInt();
                int x = scanner.nextInt();
                int darkness = scanner.nextInt();
                grid[y][x] = darkness;
                drops[j] = new int[]{y, x};
            }
            BleedingInk bleedingInk = new BleedingInk(grid, drops);
            System.out.println(bleedingInk.solve());
        }
    }

    public int solve() {
        for (int[] drop : drops) {
            bfs(drop[0], drop[1]);
        }
        int result = 0;
        for (int[] row : grid) {
            for (int x : row) {
                result += x;
            }
        }
        return result;
    }

    private boolean isStateValid(State s) {
        return s.y < grid.length && s.x < grid[0].length && s.y >= 0 && s.x >= 0 && s.parentDarkness > 0;
    }

    private void visitState(State s) {
        int parrentDarkness = s.parentDarkness;
        int currentDarkness = grid[s.y][s.x];
        grid[s.y][s.x] = Math.max(Math.max(parrentDarkness - 1, currentDarkness), 0);
        visited[s.y][s.x] = true;
    }

    private ArrayList<State> extendState(State s) {
        ArrayList<State> result = new ArrayList<>();
        if (grid[s.y][s.x] < 1) return result;
        int[] dy = {-1, 0, 1, 0}; // up,right, down, left
        int[] dx = {0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            State newState = new State(s.x + dx[i], s.y + dy[i], grid[s.y][s.x]);
            if (isStateValid(newState) && !visited[s.y + dy[i]][s.x + dx[i]]) {
                result.add(newState);
            }
        }
        return result;
    }

    private void bfs(int y, int x) {
        Queue<State> q = new LinkedList<>();
        for (boolean[] row : visited) {
            Arrays.fill(row, false);
        }
        State startState = new State(x, y, 1);
        if (isStateValid(startState)) q.offer(startState);
        while (!q.isEmpty()) {
            State s = q.poll();
            visitState(s);

            ArrayList<State> newStates = extendState(s);
            for (State newState : newStates) {
                q.offer(newState);
            }
        }
    }
}