class Solution {
    
    static int R;
	static int C;

	public static class Node {

		int x;
		int y;

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

	public static boolean checkDelimiter(Node node) {
		return node.x == -1 && node.y == -1;
	}

	public static boolean checkValidCell(int i, int j) {

		return i >= 0 && i < R && j >= 0 && j < C;
	}

	public static boolean checkAll(int[][] arr) {
		for (int i = 0; i < R; i++)
			for (int j = 0; j < C; j++)
				if (arr[i][j] == 1)
					return true;
		return false;
	}
    
    
    public static int orangesRotting(int[][] arr) {
        
        R = arr.length;
		for (int i = 0; i < arr.length; i++) {
			C = arr[i].length > C ? arr[i].length : C;
		}
        
		Queue<Node> queue = new LinkedList<>();
		int timeRequired = 0;
		Node temp;
		for (int i = 0; i < R; i++)
			for (int j = 0; j < C; j++)
				if (arr[i][j] == 2)
					queue.add(new Node(i, j));

		// Seperator for oranges which will be rotten after
		queue.add(new Node(-1, -1));

		while (!queue.isEmpty()) {

			boolean rotten = false;

			while (!checkDelimiter(queue.peek())) {
				temp = queue.peek();

				if (checkValidCell(temp.x + 1, temp.y)
						&& arr[temp.x + 1][temp.y] == 1) {

					if (!rotten) {
						rotten = true;
						timeRequired++;
					}

					arr[temp.x + 1][temp.y] = 2;

					queue.add(new Node(temp.x + 1, temp.y));
				}

				if (checkValidCell(temp.x - 1, temp.y)
						&& arr[temp.x - 1][temp.y] == 1) {

					if (!rotten) {
						rotten = true;
						timeRequired++;
					}

					arr[temp.x - 1][temp.y] = 2;

					queue.add(new Node(temp.x - 1, temp.y));
				}

				if (checkValidCell(temp.x, temp.y + 1)
						&& arr[temp.x][temp.y + 1] == 1) {

					if (!rotten) {
						rotten = true;
						timeRequired++;
					}

					arr[temp.x][temp.y + 1] = 2;

					queue.add(new Node(temp.x, temp.y + 1));
				}

				if (checkValidCell(temp.x, temp.y - 1)
						&& arr[temp.x][temp.y - 1] == 1) {

					if (!rotten) {
						rotten = true;
						timeRequired++;
					}

					arr[temp.x][temp.y - 1] = 2;

					queue.add(new Node(temp.x, temp.y - 1));
				}

				queue.remove();
				if (rotten) {
					queue.add(new Node(-1, -1));
				}

			}
			queue.remove();
		}
		return checkAll(arr) ? -1 : timeRequired;
    }
}