1class Solution {
2    /**
3     * Performs a multi-source BFS flood fill on an n x m grid.
4     * Each source paints the grid with its own color, expanding one ring per round.
5     * When multiple sources reach the same empty cell in the same round,
6     * the cell takes the maximum color value among the competing sources.
7     *
8     * @param n       number of rows
9     * @param m       number of columns
10     * @param sources array of sources, each as {row, col, color}
11     * @return the fully colored grid
12     */
13    public int[][] colorGrid(int n, int m, int[][] sources) {
14        // Resulting grid; 0 means "not yet colored".
15        int[][] ans = new int[n][m];
16
17        // Current BFS frontier; each element is {row, col, color}.
18        List<int[]> queue = new ArrayList<>();
19
20        // Direction offsets for up, right, down, left (paired as dirs[i], dirs[i+1]).
21        int[] dirs = {-1, 0, 1, 0, -1};
22
23        // Initialize the grid and the frontier with all the sources.
24        for (int[] source : sources) {
25            int row = source[0];
26            int col = source[1];
27            int color = source[2];
28            ans[row][col] = color;
29            queue.add(new int[] {row, col, color});
30        }
31
32        // Expand the frontier one ring at a time until no new cells can be colored.
33        while (!queue.isEmpty()) {
34            // For this round, map each candidate cell (encoded as a key) to the
35            // maximum color that wants to occupy it.
36            Map<Long, Integer> candidates = new HashMap<>();
37
38            for (int[] current : queue) {
39                int row = current[0];
40                int col = current[1];
41                int color = current[2];
42
43                // Try to expand into each of the four neighbors.
44                for (int i = 0; i < 4; i++) {
45                    int nextRow = row + dirs[i];
46                    int nextCol = col + dirs[i + 1];
47
48                    // Only consider in-bounds cells that are still uncolored.
49                    if (nextRow >= 0 && nextRow < n
50                            && nextCol >= 0 && nextCol < m
51                            && ans[nextRow][nextCol] == 0) {
52                        // Encode (nextRow, nextCol) as a single long key.
53                        long key = (long) nextRow * m + nextCol;
54                        // Keep the largest color competing for this cell.
55                        candidates.put(key, Math.max(candidates.getOrDefault(key, 0), color));
56                    }
57                }
58            }
59
60            // Build the next frontier by committing the winning colors.
61            queue.clear();
62            for (Map.Entry<Long, Integer> entry : candidates.entrySet()) {
63                long key = entry.getKey();
64                int row = (int) (key / m);
65                int col = (int) (key % m);
66                int color = entry.getValue();
67
68                // Paint the cell and add it to the next round's frontier.
69                ans[row][col] = color;
70                queue.add(new int[] {row, col, color});
71            }
72        }
73
74        return ans;
75    }
76}
77

1class Solution {
2public:
3    vector<vector<int>> colorGrid(int n, int m, vector<vector<int>>& sources) {
4        // Result grid initialized to 0 (uncolored).
5        vector<vector<int>> ans(n, vector<int>(m, 0));
6
7        // BFS frontier: each entry holds {row, col, color}.
8        vector<array<int, 3>> queue;
9
10        // Direction offsets for the 4 neighbors (up, right, down, left).
11        // Read consecutive pairs: (-1,0), (0,1), (1,0), (0,-1).
12        int dirs[] = {-1, 0, 1, 0, -1};
13
14        // Seed the BFS with all source cells and color them immediately.
15        for (auto& source : sources) {
16            ans[source[0]][source[1]] = source[2];
17            queue.push_back({source[0], source[1], source[2]});
18        }
19
20        // Multi-source BFS, processed level by level so cells reached at the
21        // same distance are resolved together.
22        while (!queue.empty()) {
23            // For the current level, record the best (largest) candidate color
24            // for each uncolored neighbor cell, keyed by a flattened index.
25            unordered_map<long long, int> visited;
26
27            for (auto& current : queue) {
28                int row = current[0], col = current[1], color = current[2];
29
30                // Explore the 4 orthogonal neighbors.
31                for (int i = 0; i < 4; i++) {
32                    int nextRow = row + dirs[i];
33                    int nextCol = col + dirs[i + 1];
34
35                    // Only consider in-bounds, still-uncolored cells.
36                    if (nextRow >= 0 && nextRow < n &&
37                        nextCol >= 0 && nextCol < m &&
38                        ans[nextRow][nextCol] == 0) {
39                        // Flatten 2D coordinates into a single key.
40                        long long key = (long long) nextRow * m + nextCol;
41
42                        // Keep the highest color among competing sources.
43                        if (color > visited[key]) {
44                            visited[key] = color;
45                        }
46                    }
47                }
48            }
49
50            // Prepare the next BFS level from the resolved neighbor cells.
51            queue.clear();
52            for (auto const& [key, color] : visited) {
53                int row = key / m;
54                int col = key % m;
55
56                // Commit the winning color and enqueue for further expansion.
57                ans[row][col] = color;
58                queue.push_back({row, col, color});
59            }
60        }
61
62        return ans;
63    }
64};
65

1/**
2 * Performs a multi-source BFS flood fill on a grid.
3 * Each empty cell is colored by the nearest source. When multiple sources
4 * reach a cell simultaneously (same distance), the larger color value wins.
5 *
6 * @param rows    - Number of rows in the grid.
7 * @param cols    - Number of columns in the grid.
8 * @param sources - Array of sources, each as [row, col, color].
9 * @returns The fully colored grid.
10 */
11function colorGrid(rows: number, cols: number, sources: number[][]): number[][] {
12    // Initialize the result grid with all cells set to 0 (uncolored).
13    const grid: number[][] = Array.from({ length: rows }, () => Array(cols).fill(0));
14
15    // Initialize the BFS frontier with a deep copy of the source cells.
16    let frontier: number[][] = sources.map((source) => [...source]);
17
18    // Direction offsets for the four neighbors: up, right, down, left.
19    // Consecutive pairs (dirs[i], dirs[i + 1]) form (dr, dc).
20    const dirs: number[] = [-1, 0, 1, 0, -1];
21
22    // Paint all source cells with their respective colors.
23    for (const [row, col, color] of frontier) {
24        grid[row][col] = color;
25    }
26
27    // Expand the frontier outward level by level until no new cells remain.
28    while (frontier.length > 0) {
29        // Track candidate colors for each newly reachable cell at this level.
30        // Key: "row,col"; Value: the maximum color reaching that cell.
31        const candidates: Map<string, number> = new Map();
32
33        for (const [row, col, color] of frontier) {
34            // Explore the four orthogonal neighbors.
35            for (let i = 0; i < 4; i++) {
36                const nextRow = row + dirs[i];
37                const nextCol = col + dirs[i + 1];
38
39                // Only consider in-bounds cells that are still uncolored.
40                if (
41                    nextRow >= 0 &&
42                    nextRow < rows &&
43                    nextCol >= 0 &&
44                    nextCol < cols &&
45                    grid[nextRow][nextCol] === 0
46                ) {
47                    const key = `${nextRow},${nextCol}`;
48                    // Keep the largest color among all sources reaching this cell.
49                    candidates.set(key, Math.max(candidates.get(key) || 0, color));
50                }
51            }
52        }
53
54        // Build the next frontier from the resolved candidate cells.
55        frontier = [];
56        for (const [key, color] of candidates.entries()) {
57            const [nextRow, nextCol] = key.split(',').map(Number);
58            grid[nextRow][nextCol] = color;
59            frontier.push([nextRow, nextCol, color]);
60        }
61    }
62
63    return grid;
64}
65