Rust

use std::collections::{HashMap, HashSet};

use itertools::Itertools;

fn explode_from_barrel(
    map: &HashMap<(isize, isize), i8>,
    mut exploded: HashSet<(isize, isize)>,
    mut front: HashSet<(isize, isize)>,
) -> HashSet<(isize, isize)> {
    while !front.is_empty() {
        let mut next_front = HashSet::new();
        for (i, j) in front.drain() {
            exploded.insert((i, j));
            let my_size = map[&(i, j)];
            for (di, dj) in [(-1, 0), (0, -1), (0, 1), (1, 0)] {
                let (ni, nj) = (i + di, j + dj);
                if exploded.contains(&(ni, nj)) {
                    continue;
                }
                if let Some(neighour_size) = map.get(&(ni, nj))
                    && *neighour_size <= my_size
                {
                    next_front.insert((ni, nj));
                }
            }
        }
        front = next_front;
    }
    exploded
}

pub fn solve_part_1(input: &str) -> String {
    let map: HashMap<(isize, isize), i8> = input
        .lines()
        .enumerate()
        .flat_map(|(i, line)| {
            line.chars()
                .enumerate()
                .map(move |(j, ch)| ((i as isize, j as isize), ch as i8 - '0' as i8))
        })
        .collect();
    let exploded = HashSet::<(isize, isize)>::new();
    let front: HashSet<(isize, isize)> = [(0, 0)].into_iter().collect();
    explode_from_barrel(&map, exploded, front).len().to_string()
}

pub fn solve_part_2(input: &str) -> String {
    let map: HashMap<(isize, isize), i8> = input
        .lines()
        .enumerate()
        .flat_map(|(i, line)| {
            line.chars()
                .enumerate()
                .map(move |(j, ch)| ((i as isize, j as isize), ch as i8 - '0' as i8))
        })
        .collect();
    let exploded = HashSet::<(isize, isize)>::new();
    let max_i = map.keys().map(|(i, _)| *i).max().unwrap();
    let max_j = map.keys().map(|(_, j)| *j).max().unwrap();
    let front: HashSet<(isize, isize)> = [(0, 0), (max_i, max_j)].into_iter().collect();
    explode_from_barrel(&map, exploded, front).len().to_string()
}

pub fn solve_part_3(input: &str) -> String {
    let map: HashMap<(isize, isize), i8> = input
        .lines()
        .enumerate()
        .flat_map(|(i, line)| {
            line.chars()
                .enumerate()
                .map(move |(j, ch)| ((i as isize, j as isize), ch as i8 - '0' as i8))
        })
        .collect();
    let max_i = map.keys().map(|(i, _)| *i).max().unwrap();
    let max_j = map.keys().map(|(_, j)| *j).max().unwrap();
    let best_barrel = (0..=max_i)
        .cartesian_product(0..=max_j)
        .map(|(i, j)| {
            ((i, j), {
                let exploded = HashSet::<(isize, isize)>::new();
                let front: HashSet<(isize, isize)> = [(i, j)].into_iter().collect();
                explode_from_barrel(&map, exploded, front)
            })
        })
        .max_by_key(|(_, exploded)| exploded.len())
        .unwrap();
    let second_best_barrel = (0..=max_i)
        .cartesian_product(0..=max_j)
        .filter(|&(i, j)| !best_barrel.1.contains(&(i, j)))
        .map(|(i, j)| {
            ((i, j), {
                let exploded = best_barrel.1.clone();
                let front: HashSet<(isize, isize)> = [(i, j)].into_iter().collect();
                explode_from_barrel(&map, exploded, front)
            })
        })
        .max_by_key(|(_, exploded)| exploded.len())
        .unwrap();
    let third_best_barrel = (0..=max_i)
        .cartesian_product(0..=max_j)
        .filter(|&(i, j)| !second_best_barrel.1.contains(&(i, j)))
        .map(|(i, j)| {
            ((i, j), {
                let exploded = second_best_barrel.1.clone();
                let front: HashSet<(isize, isize)> = [(i, j)].into_iter().collect();
                explode_from_barrel(&map, exploded, front)
            })
        })
        .max_by_key(|(_, exploded)| exploded.len())
        .unwrap();
    let exploded = HashSet::<(isize, isize)>::new();
    let front: HashSet<(isize, isize)> = [best_barrel.0, second_best_barrel.0, third_best_barrel.0]
        .into_iter()
        .collect();
    explode_from_barrel(&map, exploded, front).len().to_string()
}

Python

# get all valid neighbors of a cell in a grid
DELTAS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def getNeighbors(i, j, m, n):
    for di, dj in DELTAS:
        ni, nj = i + di, j + dj
        if 0 <= ni < m and 0 <= nj < n:
            yield ni, nj

# constant for marking permanently burnt cells
PERMA_BURNT = -1

# DFS to burn the grid from a list of starting points
# If perma_burn is True, cells that are burnt will be modified to PERMA_BURNT
# returns the set of all burnt cells
def dfs_burn(grid: list[list[int]], start: list[tuple[int, int]], perma_burn=False) -> set[tuple[int, int]]:
    m, n = len(grid), len(grid[0])

    ignited = start
    burnt = set()

    while ignited:
        i, j = ignited.pop()
        if (i, j) in burnt:
            continue
        burnt.add((i, j))

        for ni, nj in getNeighbors(i, j, m, n):
            if (ni, nj) in burnt or grid[ni][nj] == PERMA_BURNT:
                continue
            if grid[ni][nj] <= grid[i][j]:
                ignited.append((ni, nj))
        
        # mark as permanently burnt (if requested)
        if perma_burn: grid[i][j] = PERMA_BURNT
    return burnt

# Part 1: DFS burn from single source (0, 0)
def part1(data: str) -> int:
    grid = [[int(c) for c in row] for row in data.splitlines()]
    return len(dfs_burn(grid, [(0, 0)]))

assert part1("""989601
857782
746543
766789""") == 16

# Part 2: DFS burn from two sources (0,0) and (m-1,n-1)
def part2(data: str) -> int:
    grid = [[int(c) for c in row] for row in data.splitlines()]
    m, n = len(grid), len(grid[0])
    return len(dfs_burn(grid, [(0, 0), (m - 1, n - 1)]))

assert part2("""9589233445
9679121695
8469121876
8352919876
7342914327
7234193437
6789193538
6781219648
5691219769
5443329859""") == 58

from copy import deepcopy

# Part 3: Greedy selection of three best burn points
def part3(data: str) -> int:
    grid = [[int(c) for c in row] for row in data.splitlines()]
    m, n = len(grid), len(grid[0])
    # keep original grid for final burn count
    og_grid = deepcopy(grid)

    # generate the list of best burn candidates
    # note that the cell with the max value is not necessarily the single best burn point
    # this will help us skip the cells that are clearly suboptimal
    candidates = [(grid[i][j], i, j) for i in range(m) for j in range(n)]
    candidates.sort(reverse=True)

    # best three burn points (separately chosen)
    best_three = []

    for _ in range(3):
        # set of all cells burnt in this iteration
        burnt = set()

        # track the best burn location in this iteration
        max_burnt = 0
        max_burn_loc = None

        for _, i, j in candidates:
            # skip candidates that are already burnt by a previous burn point
            # this is because a previous burn point will contain all the burns of this candidate
            #   plus possibly more
            if (i, j) in burnt:
                continue
            # burn (impermanently) from this candidate
            burns = dfs_burn(grid, [(i, j)])
            if len(burns) > max_burnt:
                max_burnt = len(burns)
                max_burn_loc = (i, j)
            # record newly burnt cells to skip in future candidates
            burnt |= burns
        
        assert max_burn_loc is not None, "Should have found a max burn location"
        # record and permanently burn from the best location found
        dfs_burn(grid, [max_burn_loc], perma_burn=True)
        best_three.append(max_burn_loc)
    
    # return total burnt cells from all three best burn points simultaneously
    return len(dfs_burn(og_grid, best_three))

assert (t := part3("""5411
3362
5235
3112""")) == 14, f"Expected: 14, Actual: {t}"

assert (t := part3("""41951111131882511179
32112222211518122215
31223333322115122219
31234444432147511128
91223333322176121892
61112222211166431583
14661111166111111746
11111119142122222177
41222118881233333219
71222127839122222196
56111126279711111517""")) == 136, f"Expected: 136, Actual: {t}"