Multi Source Flood Fill | Leetcode 3905

class Solution {
    #define pii pair<int,int>
    static constexpr int dir[5] = {-1,0,1,0,-1};
public:
    vector<vector<int>> colorGrid(int n, int m, vector<vector<int>>& sources) {
        sort(sources.begin(),sources.end(),[](const vector<int>& a,const vector<int>& b){
            return a[2]>b[2];
        });
        vector<vector<int>> grid(n,vector<int>(m));
        queue<pii> q;
        for(auto& source: sources){
            q.push({source[0],source[1]});
            grid[source[0]][source[1]] = source[2];
        }
        
        while(!q.empty()){
            auto [x,y] = q.front();
            q.pop();

            //check 4 dirs
            for(int d=0;d<4;++d){
                int newX = x + dir[d];
                int newY = y + dir[d+1];
                if(newX>=0 and newX<n and newY>=0 and newY<m and grid[newX][newY]==0){
                    grid[newX][newY] = grid[x][y];
                    q.push({newX,newY});
                }
            }
        }
        return grid;
    }
};

/*
//JAVA
import java.util.*;

class Solution {
    public int[][] colorGrid(int n, int m, int[][] sources) {
        // Sort sources by color value in descending order
        Arrays.sort(sources, (a, b) -> Integer.compare(b[2], a[2]));

        int[][] grid = new int[n][m];
        Queue<int[]> q = new LinkedList<>();
        int[] dir = {-1, 0, 1, 0, -1};

        for (int[] source : sources) {
            int r = source[0];
            int c = source[1];
            int color = source[2];
            
            // Initial source placement
            if (grid[r][c] == 0) {
                grid[r][c] = color;
                q.offer(new int[]{r, c});
            }
        }

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int x = curr[0];
            int y = curr[1];

            for (int i = 0; i < 4; i++) {
                int newX = x + dir[i];
                int newY = y + dir[i + 1];

                if (newX >= 0 && newX < n && newY >= 0 && newY < m && grid[newX][newY] == 0) {
                    grid[newX][newY] = grid[x][y];
                    q.offer(new int[]{newX, newY});
                }
            }
        }

        return grid;
    }
}

#Python
from collections import deque

class Solution:
    def colorGrid(self, n: int, m: int, sources: list[list[int]]) -> list[list[int]]:
        # Sort sources by color value in descending order
        sources.sort(key=lambda x: x[2], reverse=True)

        grid = [[0] * m for _ in range(n)]
        queue = deque()
        directions = [-1, 0, 1, 0, -1]

        for r, c, color in sources:
            if grid[r][c] == 0:
                grid[r][c] = color
                queue.append((r, c))

        while queue:
            x, y = queue.popleft()

            for i in range(4):
                new_x = x + directions[i]
                new_y = y + directions[i + 1]

                if 0 <= new_x < n and 0 <= new_y < m and grid[new_x][new_y] == 0:
                    grid[new_x][new_y] = grid[x][y]
                    queue.append((new_x, new_y))

        return grid
*/