Minimum time required to rot all oranges

Question

Given a matrix of dimension r*c where each cell in the matrix can have values 0, 1 or 2 which has the following meaning: 0 : Empty cell 1 : Cells have fresh oranges 2 : Cells have rotten oranges

So, we have to determine what is the minimum time required to rot all oranges. A rotten orange at index [i,j] can rot other fresh orange at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right) in unit time. If it is impossible to rot every orange then simply return -1.

Input: The first line of input contains an integer T denoting the number of test cases. Each test case contains two integers r and c, where r is the number of rows and c is the number of columns in the array a[]. Next line contains space separated r*c elements each in the array a[].
Here is the Code I have written

class GFG {

    public static boolean isSafe(int[][] M, boolean[][] visited, int i, int j) {
        int R = M.length;
        int C = M[0].length;
        return (i >= 0 && i < R && j >= 0 && j < C && (!visited[i][j]) && M[i][j] != 0);
    }

    public static int findMinDist(int[][] M, boolean[][] visited, int i, int j, int dist) {
        if (M[i][j] == 2)
            return dist;
        int[] x_pos = { 1, -1, 0, 0 };
        int[] y_pos = { 0, 0, -1, 1 };
        visited[i][j] = true;
        int min = Integer.MAX_VALUE;
        for (int k = 0; k < 4; k++) {
            if (isSafe(M, visited, i + x_pos[k], j + y_pos[k]))
                min = Math.min(min, findMinDist(M, visited, i + x_pos[k], j + y_pos[k], dist + 1));
        }
        return min;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            int R = sc.nextInt();
            int C = sc.nextInt();
            int[][] M = new int[R][C];
            boolean[][] visited = new boolean[R][C];
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    M[i][j] = sc.nextInt();
                }
            }
            int[][] time = new int[R][C];
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (M[i][j] == 1)
                        time[i][j] = findMinDist(M, new boolean[R][C], i, j, 0);
                }
            }
            int maxTime = Integer.MIN_VALUE;
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    maxTime = Math.max(time[i][j], maxTime);
                }
            }
            System.out.println(maxTime == Integer.MAX_VALUE ? -1 : maxTime);
        }
    }
}

I am trying to find minimum distance of 2 from each 1.
It is not working for test case
Input:
1
2 5
1 1 1 1 1 0 2 1 1 1

Its Correct output is:
4

And My Code's output is:
6

Please suggest what's wrong with the code.

Answer 1

Start by creating a matrix to store the times the oranges rot. You can initialize all slots with -1. You will use BFS but you won't need a "marked" matrix, because the times the oranges rot will already be enough to tell you if a slot has been visited or not.

Iterate through the original matrix. When you find a value 2, do a BFS starting there to rot the fresh oranges. This BFS should also state the time when each orange is rot and you must always keep the smallest time. If the orange being looked at the moment was already rotten at time t1 and you've just got there in time t2, where t2 < t1, pretend this orange is fresh and put it into the BFS queue like so.

After finishing it, iterate through the matrix of times and return the biggest value found.

Answer 2

class Pair {

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int x;
    public int y;
}

public class Solution {

    public static boolean isSafe(int x, int y, int r, int c) {
        return (x >= 0) && (x < r) && (y >= 0) && (y < c);
    }

    public static boolean isFreshOrageLeft(int[][] grid) {
        int r = grid.length;
        int c = grid[0].length;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == 1)
                    return true;
            }
        }
        return false;
    }

    public static int orangesRotting(int[][] grid) {

        int r = grid.length;
        int c = grid[0].length;

        int count = 0;
        boolean flag = false;

        Queue<Pair> q = new LinkedList<>();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == 2)
                    q.add(new Pair(i, j));
            }
        }

        q.add(new Pair(-1, -1));

        while (!q.isEmpty()) {
            while (q.peek().x != -1 && q.peek().y != -1) {

                Pair p = q.poll();
                int leftX = p.x - 1;
                int leftY = p.y;
                if (isSafe(leftX, leftY, r, c) && grid[leftX][leftY] == 1) {
                    if (!flag) {
                        count++;
                        flag = true;
                    }
                    grid[leftX][leftY] = 2;
                    q.add(new Pair(leftX, leftY));
                }

                int rightX = p.x + 1;
                int rightY = p.y;
                if (isSafe(rightX, rightY, r, c) && grid[rightX][rightY] == 1) {
                    if (!flag) {
                        count++;
                        flag = true;
                    }
                    grid[rightX][rightY] = 2;
                    q.add(new Pair(rightX, rightY));
                }

                int upX = p.x;
                int upY = p.y + 1;
                if (isSafe(upX, upY, r, c) && grid[upX][upY] == 1) {
                    if (!flag) {
                        count++;
                        flag = true;
                    }
                    grid[upX][upY] = 2;
                    q.add(new Pair(upX, upY));
                }

                int downX = p.x;
                int downY = p.y - 1;
                if (isSafe(downX, downY, r, c) && grid[downX][downY] == 1) {
                    if (!flag) {
                        count++;
                        flag = true;
                    }
                    grid[downX][downY] = 2;
                    q.add(new Pair(downX, downY));
                }
            }
            flag = false;
            q.poll();
            if (!q.isEmpty())
                q.add(new Pair(-1, -1));
        }

        return isFreshOrageLeft(grid)?-1:count;
    }

    public static void main(String[] args) {
        int[][] grid = {{2,2,0,1}};
        System.out.println(orangesRotting(grid));
    }

}