Grid Coloring - Google Top Interview Questions

                        Solution in C++ :

int solve(vector<vector<int>>& matrix) {
    int n = matrix.size(), m = matrix[0].size();
    vector<vector<int>> f(n, vector<int>(m, 1000010000));
    struct State {
        int r, c, f;
        bool operator<(const State& that) const {
            return f > that.f;
        }
    };
    priority_queue<State> q;
    q.push({0, 0, 0});
    f[0][0] = 0;
    int ret = 0;
    const int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
    while (!q.empty()) {
        const auto curr = q.top();
        q.pop();
        if (curr.f > f[curr.r][curr.c]) continue;
        // cout << curr.r << ' ' << curr.c << ' ' << curr.f << endl;
        for (int d = 0; d < 4; ++d) {
            State next = {curr.r + dr[d], curr.c + dc[d], curr.f};
            if (next.r < 0 || next.r >= n) continue;
            if (next.c < 0 || next.c >= m) continue;
            if (matrix[next.r][next.c] != matrix[curr.r][curr.c]) ++next.f;
            if (next.f < f[next.r][next.c]) {
                f[next.r][next.c] = next.f;
                q.push(next);
                ret = max(ret, next.f);
            }
        }
    }
    /*
    for (const auto& v : f) {
        for (int x : v) cout << x << ' ';
        cout << endl;
    }
    */
    return ret;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    final int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public int solve(int[][] matrix) {
        if (matrix.length == 0)
            return 0;
        // q represents the current list of coordinates of islands we want to floodfill from
        Queue<int[]> q = new LinkedList();
        q.offer(new int[] {0, 0});

        // curr represents the id of the island we are trying to floodfill. this value will
        // alternate between 1 and 0 indefinitely until the problem is solved
        int curr = matrix[0][0];

        // next is the queue that we add the coordinates of "borders" into. We will then loop
        // through these values in our "next round" of floodfill
        Queue<int[]> next = new LinkedList();

        // visited array
        boolean[][] vis = new boolean[matrix.length][matrix[0].length];

        vis[0][0] = true;
        int ret = 0;
        while (!q.isEmpty()) {
            // loop through queue and add all of the borders to the other queue "next"
            while (!q.isEmpty()) {
                int size = q.size();
                int[] temp = q.poll();
                int i = temp[0];
                int j = temp[1];

                for (int[] d : dirs) {
                    int neighI = i + d[0];
                    int neighJ = j + d[1];

                    // out of bounds check
                    if (neighI < 0 || neighJ < 0 || neighI >= matrix.length
                        || neighJ >= matrix[0].length || vis[neighI][neighJ])
                        continue;

                    vis[neighI][neighJ] = true;
                    if (matrix[neighI][neighJ] == curr) {
                        q.add(new int[] {neighI, neighJ});

                    } else {
                        next.offer(new int[] {neighI, neighJ});
                    }
                }
            }

            ret++;
            curr = 1 - curr;

            // swapping the two queues
            Queue<int[]> temp1 = new LinkedList();
            Queue<int[]> temp2 = new LinkedList();

            temp1.addAll(q);
            temp2.addAll(next);

            q = temp2;
            next = temp1;
        }
        return ret - 1;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, matrix):
        if not matrix or not matrix[0]:
            return 0

        m, n = len(matrix), len(matrix[0])
        is_filled = [[False] * n for _ in range(m)]
        is_filled[0][0] = True
        operation_count = -1
        layer = [(0, 0)]

        while layer:
            operation_count += 1
            next_layer = []
            while layer:
                y, x = layer.pop()
                for y2, x2 in [(y - 1, x), (y, x + 1), (y + 1, x), (y, x - 1)]:
                    if not 0 <= y2 < m or not 0 <= x2 < n:
                        continue
                    if is_filled[y2][x2]:
                        continue
                    is_filled[y2][x2] = True
                    if matrix[y2][x2] == matrix[y][x]:
                        layer.append((y2, x2))
                    else:
                        next_layer.append((y2, x2))
            layer = next_layer

        return operation_count