Standard Priority Queue VIII: Two Queues

This is an interesting problem where you do need a priority queue in order to simulate the game (remember to use Max-Color as the priority since the dequeuing is based on smaller priorities first), but the tricky part here is that you cannot enqueue in the main loop while each round simulation is going on otherwise you'll starve lower priority colors. Hence in the middle of the main simulation loop, instead of enqueuing, just save off the elements to be enqueued later. I used another pQueue for this reason, but you could have used a different data structure, pQueues are not necessary here. Code is down below, cheers, ACC.

Multi Source Flood Fill - LeetCode

You are given two integers n and m representing the number of rows and columns of a grid, respectively.

You are also given a 2D integer array sources, where sources[i] = [ri, ci, color​​​​​​​i] indicates that the cell (ri, ci) is initially colored with colori. All other cells are initially uncolored and represented as 0.

At each time step, every currently colored cell spreads its color to all adjacent uncolored cells in the four directions: up, down, left, and right. All spreads happen simultaneously.

If multiple colors reach the same uncolored cell at the same time step, the cell takes the color with the maximum value.

The process continues until no more cells can be colored.

Return a 2D integer array representing the final state of the grid, where each cell contains its final color.

 

Example 1:

Input: n = 3, m = 3, sources = [[0,0,1],[2,2,2]]

Output: [[1,1,2],[1,2,2],[2,2,2]]

Explanation:

The grid at each time step is as follows:

​​​​​​​

At time step 2, cells (0, 2), (1, 1), and (2, 0) are reached by both colors, so they are assigned color 2 as it has the maximum value among them.

Example 2:

Input: n = 3, m = 3, sources = [[0,1,3],[1,1,5]]

Output: [[3,3,3],[5,5,5],[5,5,5]]

Explanation:

The grid at each time step is as follows:

Example 3:

Input: n = 2, m = 2, sources = [[1,1,5]]

Output: [[5,5],[5,5]]

Explanation:

The grid at each time step is as follows:

​​​​​​​

Since there is only one source, all cells are assigned the same color.

 

Constraints:

• 1 <= n, m <= 105
• 1 <= n * m <= 105
• 1 <= sources.length <= n * m
• sources[i] = [ri, ci, colori]
• 0 <= ri <= n - 1
• 0 <= ci <= m - 1
• 1 <= colori <= 106​​​​​​​
• All (ri, ci​​​​​​​) in sources are distinct.

public class Solution {
    public int[][] ColorGrid(int n, int m, int[][] sources)
    {
        int[][] retVal = new int[n][];
        for (int i = 0; i < n; i++) retVal[i] = new int[m];

        PriorityQueue pQueue = new PriorityQueue();
        long MOD = 1000000 + 7;

        //Enqueue in a pQueue
        for (int i = 0; i < sources.Length; i++)
        {
            int row = sources[i][0];
            int col = sources[i][1];
            int color = sources[i][2];
            retVal[row][col] = color;

            long key = row * MOD + col;
            long priority = MOD - color;
            pQueue.Enqueue(key, priority);
        }

        //Dequeue and process
        while (pQueue.Count > 0)
        {
            PriorityQueue nextPQueue = new PriorityQueue();

            while (pQueue.Count > 0)
            {
                long key = pQueue.Dequeue();
                int row = (int)(key / MOD);
                int col = (int)(key % MOD);

                int[] rowDelta = { 1, -1, 0, 0 };
                int[] colDelta = { 0, 0, 1, -1 };

                for (int i = 0; i < rowDelta.Length; i++)
                {
                    int nextRow = row + rowDelta[i];
                    int nextCol = col + colDelta[i];

                    if (nextRow >= 0 &&
                        nextRow < n &&
                        nextCol >= 0 &&
                        nextCol < m &&
                        retVal[nextRow][nextCol] == 0)
                    {
                        retVal[nextRow][nextCol] = retVal[row][col];

                        long nextKey = nextRow * MOD + nextCol;
                        long nextPriority = MOD - retVal[row][col];
                        nextPQueue.Enqueue(nextKey, nextPriority);
                    }
                }
            }

            while (nextPQueue.Count > 0)
            {
                long key = nextPQueue.Dequeue();
                int row = (int)(key / MOD);
                int col = (int)(key % MOD);
                long priority = MOD - retVal[row][col];

                pQueue.Enqueue(key, priority);
            }
        }

        return retVal;
    }
}