Skip to main content

Minimum time required to rot all oranges

Here given code implementation process.

/*
    Java Program for
    Minimum time required to rot all oranges
*/

import java.util.LinkedList;

import java.util.Queue;

class Position
{
    public int row;
    public int col;
    public Position(int row, int col)
    {
        this.row = row;
        this.col = col;
    }
}
public class Timing
{
    public int minTimeToRot(int[][] mat)
    {
        // Number of row
        int n = mat.length;
        // Number of columns
        int m = mat[0].length;

        Queue < Position > queue = new LinkedList <Position> ();
        
        // Define some auxliary variables
        int size = 0;
        int time = 0;
        int tempRow = 0;
        int tempCol = 0;
        boolean result = true;
        
        // Add cordinate of rot oranges
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (mat[i][j] == 2)
                {
                    queue.add(new Position(i, j));
                }
            }
        }
        // Execute this loop unit when queue not empty and result is true
        while (!queue.isEmpty() && result == true)
        {
            // Get the size of queue
            size = queue.size();

            // Change result
            result = false;
     

            // Check of all 4 Direction of rot orange
            // Note size is based on queue size
            for (int i = 0; i < size; i++)
            {
                // Get queue element
                Position curr = queue.peek();

             
                // Remove queue element
                queue.remove();
            

                // Up element adjustment 
                // Get the position of row and columns
                tempRow = curr.row - 1;
                tempCol = curr.col; 

                if ((tempRow >= 0 && tempRow < n) && 
                    (tempCol >= 0 && tempCol < m) && 
                      mat[tempRow][tempCol] == 1)
                {
                
                    // Add change coordinate
                    queue.add(new Position(tempRow, tempCol));

                    // Fresh orange to rot orange  
                    mat[tempRow][tempCol] = 2;
                    
                    // When change orange
                    result = true;
             
                }
            
                // Change row
                tempRow = curr.row + 1;
                tempCol = curr.col; 
                // Down element adjustment 
                if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
                {
                    
                    // Change right orange
                    // Fresh orange to rot orange  
                    mat[tempRow][tempCol] = 2;

                    // Add change cordinate
                    queue.add(new Position(tempRow, tempCol));
                    // When change orange
                    result = true;
                  
                }
      
                // Change columns
                tempRow = curr.row ;
                tempCol = curr.col + 1;
                // Right element adjustment 
                if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
                {
                    // Add change coordinate
                    queue.add(new Position(tempRow, tempCol));
                    // Fresh orange to rot orange  
                    mat[tempRow][tempCol] = 2;
                    // When change orange
                    result = true;
                
                }
                // Change row
                tempRow = curr.row;
                // Change columns
                tempCol = curr.col - 1;
                // Left element
                if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
                {
                    
                    // Add change coordinate
                    queue.add(new Position(tempRow, tempCol));
                    // change orange 1 to 2
                    // Fresh orange to rot orange  
                    mat[tempRow][tempCol] = 2;
                    // When change orange
                    result = true;
                    
                }
            }
            
            if (result) 
            {
                time++;
            }
           
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (mat[i][j] == 1) 
                {
                    // In case when orange are not rot
                    return -1;
                }
            }
        }
        return time;
    }
    public static void main(String[] args)
    {
        Timing t = new Timing();
   
        int [][]mat1 = 
        {
            {
                0 , 1 , 1, 2
            },
            {
                0 , 1 , 0, 0
            },
            {
                0 , 0 , 1, 0
            },
            {
                0 , 1 , 2, 0
            }
        };
        int [][]mat2 =
        {
            {
                1 , 0 , 1, 0
            },
            {
                2 , 0 , 2, 1
            },
            {
                1 , 0 , 0, 0
            }
        };
        int [][]mat3 =
        {
            {
                1 , 0 , 1 
            },
            {
                0 , 2 , 0
            },
            {
                1 , 0 , 1
            }
        };
        System.out.println("Result mat1 : "+t.minTimeToRot(mat1));
        System.out.println("Result mat2 : "+t.minTimeToRot(mat2));
        System.out.println("Result mat3 : "+t.minTimeToRot(mat3));
    }
}

Output

Result mat1 : 3
Result mat2 : 1
Result mat3 : -1
// Include header file
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class Position
{
	public: int row;
	int col;
	Position(int row, int col)
	{
		this->row = row;
		this->col = col;
	}
};
class Timing
{
	public: int minTimeToRot(vector<vector<int>> &mat)
	{
		// Number of row
		int n = mat.size();
		// Number of columns
		int m = mat[0].size();
		queue < Position *> queue;
		// Define some auxliary variables
		int size = 0;
		int time = 0;
		int tempRow = 0;
		int tempCol = 0;
		bool result = true;
		// Add cordinate of rot oranges
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (mat[i][j] == 2)
				{
					queue.push(new Position(i, j));
				}
			}
		}
		// Execute this loop unit when queue not empty and result is true
		while (!queue.empty() && result == true)
		{
			// Get the size of queue
			size = queue.size();
			// Change result
			result = false;
			// Check of all 4 Direction of rot orange
			// Note size is based on queue size
			for (int i = 0; i < size; i++)
			{
				// Get queue element
				Position *curr = queue.front();
				// Remove queue element
				queue.pop();
				// Up element adjustment 
				// Get the position of row and columns
				tempRow = curr->row - 1;
				tempCol = curr->col;
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
				{
					// Add change coordinate
					queue.push(new Position(tempRow, tempCol));
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// When change orange
					result = true;
				}
				// Change row
				tempRow = curr->row + 1;
				tempCol = curr->col;
				// Down element adjustment 
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
				{
					// Change right orange
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// Add change cordinate
					queue.push(new Position(tempRow, tempCol));
					// When change orange
					result = true;
				}
				// Change columns
				tempRow = curr->row;
				tempCol = curr->col + 1;
				// Right element adjustment 
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
				{
					// Add change coordinate
					queue.push(new Position(tempRow, tempCol));
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// When change orange
					result = true;
				}
				// Change row
				tempRow = curr->row;
				// Change columns
				tempCol = curr->col - 1;
				// Left element
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
				{
					// Add change coordinate
					queue.push(new Position(tempRow, tempCol));
					// change orange 1 to 2
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// When change orange
					result = true;
				}
			}
			if (result)
			{
				time++;
			}
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (mat[i][j] == 1)
				{
					// In case when orange are not rot
					return -1;
				}
			}
		}
		return time;
	}
};
int main()
{
	Timing *t = new Timing();
	vector<vector<int>> mat1{
		{
			0 , 1 , 1 , 2
		} , {
			0 , 1 , 0 , 0
		} , {
			0 , 0 , 1 , 0
		} , {
			0 , 1 , 2 , 0
		}
	};
	vector<vector<int>> mat2{
		{
			1 , 0 , 1 , 0
		} , {
			2 , 0 , 2 , 1
		} , {
			1 , 0 , 0 , 0
		}
	};
	vector<vector<int>> mat3{
		{
			1 , 0 , 1
		} , {
			0 , 2 , 0
		} , {
			1 , 0 , 1
		}
	};
	cout << "Result mat1 : " << t->minTimeToRot(mat1) << endl;
	cout << "Result mat2 : " << t->minTimeToRot(mat2) << endl;
	cout << "Result mat3 : " << t->minTimeToRot(mat3) << endl;
	return 0;
}

Output

Result mat1 : 3
Result mat2 : 1
Result mat3 : -1
// Include namespace system
using System;
using System.Collections.Generic;
public class Position
{
	public int row;
	public int col;
	public Position(int row, int col)
	{
		this.row = row;
		this.col = col;
	}
}
public class Timing
{
	public int minTimeToRot(int[,] mat)
	{
		// Number of row
		int n = mat.GetLength(0);
		// Number of columns
		int m = mat.GetLength(1);
		Queue < Position > queue = new Queue < Position > ();
		// Define some auxliary variables
		int size = 0;
		int time = 0;
		int tempRow = 0;
		int tempCol = 0;
		Boolean result = true;
		// Add cordinate of rot oranges
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (mat[i,j] == 2)
				{
					queue.Enqueue(new Position(i, j));
				}
			}
		}
		// Execute this loop unit when queue not empty and result is true
		while ((queue.Count != 0) && result == true)
		{
			// Get the size of queue
			size = queue.Count;
			// Change result
			result = false;
			// Check of all 4 Direction of rot orange
			// Note size is based on queue size
			for (int i = 0; i < size; i++)
			{
				// Get queue element
				Position curr = queue.Peek();
				// Remove queue element
				queue.Dequeue();
				// Up element adjustment 
				// Get the position of row and columns
				tempRow = curr.row - 1;
				tempCol = curr.col;
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow,tempCol] == 1)
				{
					// Add change coordinate
					queue.Enqueue(new Position(tempRow, tempCol));
					// Fresh orange to rot orange  
					mat[tempRow,tempCol] = 2;
					// When change orange
					result = true;
				}
				// Change row
				tempRow = curr.row + 1;
				tempCol = curr.col;
				// Down element adjustment 
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow,tempCol] == 1)
				{
					// Change right orange
					// Fresh orange to rot orange  
					mat[tempRow,tempCol] = 2;
					// Add change cordinate
					queue.Enqueue(new Position(tempRow, tempCol));
					// When change orange
					result = true;
				}
				// Change columns
				tempRow = curr.row;
				tempCol = curr.col + 1;
				// Right element adjustment 
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow,tempCol] == 1)
				{
					// Add change coordinate
					queue.Enqueue(new Position(tempRow, tempCol));
					// Fresh orange to rot orange  
					mat[tempRow,tempCol] = 2;
					// When change orange
					result = true;
				}
				// Change row
				tempRow = curr.row;
				// Change columns
				tempCol = curr.col - 1;
				// Left element
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow,tempCol] == 1)
				{
					// Add change coordinate
					queue.Enqueue(new Position(tempRow, tempCol));
					// change orange 1 to 2
					// Fresh orange to rot orange  
					mat[tempRow,tempCol] = 2;
					// When change orange
					result = true;
				}
			}
			if (result)
			{
				time++;
			}
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (mat[i,j] == 1)
				{
					// In case when orange are not rot
					return -1;
				}
			}
		}
		return time;
	}
	public static void Main(String[] args)
	{
		Timing t = new Timing();
		int[,] mat1 = {
			{
				0 , 1 , 1 , 2
			},
			{
				0 , 1 , 0 , 0
			},
			{
				0 , 0 , 1 , 0
			},
			{
				0 , 1 , 2 , 0
			}
		};
		int[,] mat2 = {
			{
				1 , 0 , 1 , 0
			},
			{
				2 , 0 , 2 , 1
			},
			{
				1 , 0 , 0 , 0
			}
		};
		int[,] mat3 = {
			{
				1 , 0 , 1
			},
			{
				0 , 2 , 0
			},
			{
				1 , 0 , 1
			}
		};
		Console.WriteLine("Result mat1 : " + t.minTimeToRot(mat1));
		Console.WriteLine("Result mat2 : " + t.minTimeToRot(mat2));
		Console.WriteLine("Result mat3 : " + t.minTimeToRot(mat3));
	}
}

Output

Result mat1 : 3
Result mat2 : 1
Result mat3 : -1
<?php
/*
    Php Program for
    Minimum time required to rot all oranges
*/
class Position
{
	public $row;
	public $col;
	public	function __construct($row, $col)
	{
		$this->row = $row;
		$this->col = $col;
	}
}
class Timing
{
	public	function minTimeToRot($mat)
	{
		// Number of row
		$n = count($mat);
		// Number of columns
		$m = count($mat[0]);
		$queue = array();
		// Define some auxliary variables
		$size = 0;
		$time = 0;
		$tempRow = 0;
		$tempCol = 0;
		$result = true;
		// Add cordinate of rot oranges
		for ($i = 0; $i < $n; $i++)
		{
			for ($j = 0; $j < $m; $j++)
			{
				if ($mat[$i][$j] == 2)
				{
					array_unshift($queue, new Position($i, $j));
				}
			}
		}
		// Execute this loop unit when queue not empty and result is true
		while ((count($queue) > 0) && $result == true)
		{
			// Get the size of queue
			$size = count($queue);
			// Change result
			$result = false;
			// Check of all 4 Direction of rot orange
			// Note size is based on queue size
			for ($i = 0; $i < $size; $i++)
			{
				// Get queue element
				$curr = end($queue);
				// Remove queue element
				array_pop($queue);
				// Up element adjustment 
				// Get the position of row and columns
				$tempRow = $curr->row - 1;
				$tempCol = $curr->col;
				if (($tempRow >= 0 && $tempRow < $n) 
                    && ($tempCol >= 0 && $tempCol < $m) 
                    && $mat[$tempRow][$tempCol] == 1)
				{
					// Add change coordinate
					array_unshift($queue, new Position($tempRow, $tempCol));
					// Fresh orange to rot orange  
					$mat[$tempRow][$tempCol] = 2;
					// When change orange
					$result = true;
				}
				// Change row
				$tempRow = $curr->row + 1;
				$tempCol = $curr->col;
				// Down element adjustment 
				if (($tempRow >= 0 && $tempRow < $n) 
                    && ($tempCol >= 0 && $tempCol < $m) 
                    && $mat[$tempRow][$tempCol] == 1)
				{
					// Change right orange
					// Fresh orange to rot orange  
					$mat[$tempRow][$tempCol] = 2;
					// Add change cordinate
					array_unshift($queue, new Position($tempRow, $tempCol));
					// When change orange
					$result = true;
				}
				// Change columns
				$tempRow = $curr->row;
				$tempCol = $curr->col + 1;
				// Right element adjustment 
				if (($tempRow >= 0 && $tempRow < $n) 
                    && ($tempCol >= 0 && $tempCol < $m) 
                    && $mat[$tempRow][$tempCol] == 1)
				{
					// Add change coordinate
					array_unshift($queue, new Position($tempRow, $tempCol));
					// Fresh orange to rot orange  
					$mat[$tempRow][$tempCol] = 2;
					// When change orange
					$result = true;
				}
				// Change row
				$tempRow = $curr->row;
				// Change columns
				$tempCol = $curr->col - 1;
				// Left element
				if (($tempRow >= 0 && $tempRow < $n) 
                    && ($tempCol >= 0 && $tempCol < $m) 
                    && $mat[$tempRow][$tempCol] == 1)
				{
					// Add change coordinate
					array_unshift($queue, new Position($tempRow, $tempCol));
					// change orange 1 to 2
					// Fresh orange to rot orange  
					$mat[$tempRow][$tempCol] = 2;
					// When change orange
					$result = true;
				}
			}
			if ($result)
			{
				$time++;
			}
		}
		for ($i = 0; $i < $n; $i++)
		{
			for ($j = 0; $j < $m; $j++)
			{
				if ($mat[$i][$j] == 1)
				{
					// In case when orange are not rot
					return -1;
				}
			}
		}
		return $time;
	}
}

function main()
{
	$t = new Timing();
	$mat1 = array(
      array(0, 1, 1, 2), 
      array(0, 1, 0, 0), 
      array(0, 0, 1, 0), 
      array(0, 1, 2, 0)
    );
	$mat2 = array(
      array(1, 0, 1, 0), 
      array(2, 0, 2, 1), 
      array(1, 0, 0, 0)
    );
	$mat3 = array(
      array(1, 0, 1), 
      array(0, 2, 0),
      array(1, 0, 1)
    );
	echo("Result mat1 : ".$t->minTimeToRot($mat1).
		"\n");
	echo("Result mat2 : ".$t->minTimeToRot($mat2).
		"\n");
	echo("Result mat3 : ".$t->minTimeToRot($mat3).
		"\n");
}
main();

Output

Result mat1 : 3
Result mat2 : 1
Result mat3 : -1
class Position
{
	constructor(row, col)
	{
		this.row = row;
		this.col = col;
	}
}
class Timing
{
	minTimeToRot(mat)
	{
		// Number of row
		var n = mat.length;
		// Number of columns
		var m = mat[0].length;
		var queue = [];
		// Define some auxliary variables
		var size = 0;
		var time = 0;
		var tempRow = 0;
		var tempCol = 0;
		var result = true;
		// Add cordinate of rot oranges
		for (var i = 0; i < n; i++)
		{
			for (var j = 0; j < m; j++)
			{
				if (mat[i][j] == 2)
				{
					queue.push(new Position(i, j));
				}
			}
		}
		// Execute this loop unit when queue not empty and result is true
		while ((queue.length > 0) && result == true)
		{
			// Get the size of queue
			size = queue.length;
			// Change result
			result = false;
			// Check of all 4 Direction of rot orange
			// Note size is based on queue size
			for (var i = 0; i < size; i++)
			{
				// Get queue element
				var curr = queue[0];
				// Remove queue element
				queue.shift();
				// Up element adjustment 
				// Get the position of row and columns
				tempRow = curr.row - 1;
				tempCol = curr.col;
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
				{
					// Add change coordinate
					queue.push(new Position(tempRow, tempCol));
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// When change orange
					result = true;
				}
				// Change row
				tempRow = curr.row + 1;
				tempCol = curr.col;
				// Down element adjustment 
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
				{
					// Change right orange
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// Add change cordinate
					queue.push(new Position(tempRow, tempCol));
					// When change orange
					result = true;
				}
				// Change columns
				tempRow = curr.row;
				tempCol = curr.col + 1;
				// Right element adjustment 
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
				{
					// Add change coordinate
					queue.push(new Position(tempRow, tempCol));
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// When change orange
					result = true;
				}
				// Change row
				tempRow = curr.row;
				// Change columns
				tempCol = curr.col - 1;
				// Left element
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
				{
					// Add change coordinate
					queue.push(new Position(tempRow, tempCol));
					// change orange 1 to 2
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// When change orange
					result = true;
				}
			}
			if (result)
			{
				time++;
			}
		}
		for (var i = 0; i < n; i++)
		{
			for (var j = 0; j < m; j++)
			{
				if (mat[i][j] == 1)
				{
					// In case when orange are not rot
					return -1;
				}
			}
		}
		return time;
	}
}

function main()
{
	var t = new Timing();
	var mat1 = [
		[0, 1, 1, 2],
		[0, 1, 0, 0],
		[0, 0, 1, 0],
		[0, 1, 2, 0]
	];
	var mat2 = [
		[1, 0, 1, 0],
		[2, 0, 2, 1],
		[1, 0, 0, 0]
	];
	var mat3 = [
		[1, 0, 1],
		[0, 2, 0],
		[1, 0, 1]
	];
	console.log("Result mat1 : " + t.minTimeToRot(mat1));
	console.log("Result mat2 : " + t.minTimeToRot(mat2));
	console.log("Result mat3 : " + t.minTimeToRot(mat3));
}
main();

Output

Result mat1 : 3
Result mat2 : 1
Result mat3 : -1
#    Python 3 Program for
#    Minimum time required to rot all oranges
class Position :
    def __init__(self, row, col) :
        self.row = row
        self.col = col

class Timing :
    def minTimeToRot(self, mat) :
        #  Number of row
        n = len(mat)
        #  Number of columns
        m = len(mat[0])
        queue = []
        #  Define some auxliary variables
        size = 0
        time = 0
        tempRow = 0
        tempCol = 0
        result = True
        i = 0
        #  Add cordinate of rot oranges
        while (i < n) :
            j = 0
            while (j < m) :
                if (mat[i][j] == 2) :
                    queue.append(Position(i, j))
                
                j += 1
            
            i += 1
        
        #  Execute this loop unit when queue not empty and result is true
        while ((len(queue) > 0) and result == True) :
            #  Get the size of queue
            size = len(queue)
            #  Change result
            result = False
            i = 0
            #  Check of all 4 Direction of rot orange
            #  Note size is based on queue size
            while (i < size and len(queue) > 0) :
                #  Get queue element
                curr = queue[0]
                #  Remove queue element
                queue.pop(0)
                #  Up element adjustment 
                #  Get the position of row and columns
                tempRow = curr.row - 1
                tempCol = curr.col
                if ((tempRow >= 0 and tempRow < n) and 
                    (tempCol >= 0 and tempCol < m) and 
                    mat[tempRow][tempCol] == 1) :
                    #  Add change coordinate
                    queue.append(Position(tempRow, tempCol))
                    #  Fresh orange to rot orange  
                    mat[tempRow][tempCol] = 2
                    #  When change orange
                    result = True
                
                #  Change row
                tempRow = curr.row + 1
                tempCol = curr.col
                #  Down element adjustment 
                if ((tempRow >= 0 and tempRow < n) and 
                    (tempCol >= 0 and tempCol < m) and 
                    mat[tempRow][tempCol] == 1) :
                    #  Change right orange
                    #  Fresh orange to rot orange  
                    mat[tempRow][tempCol] = 2
                    #  Add change cordinate
                    queue.append(Position(tempRow, tempCol))
                    #  When change orange
                    result = True
                
                #  Change columns
                tempRow = curr.row
                tempCol = curr.col + 1
                #  Right element adjustment 
                if ((tempRow >= 0 and tempRow < n) and 
                    (tempCol >= 0 and tempCol < m) and 
                    mat[tempRow][tempCol] == 1) :
                    #  Add change coordinate
                    queue.append(Position(tempRow, tempCol))
                    #  Fresh orange to rot orange  
                    mat[tempRow][tempCol] = 2
                    #  When change orange
                    result = True
                
                #  Change row
                tempRow = curr.row
                #  Change columns
                tempCol = curr.col - 1
                #  Left element
                if ((tempRow >= 0 and tempRow < n) and 
                    (tempCol >= 0 and tempCol < m) and 
                    mat[tempRow][tempCol] == 1) :
                    #  Add change coordinate
                    queue.append(Position(tempRow, tempCol))
                    #  change orange 1 to 2
                    #  Fresh orange to rot orange  
                    mat[tempRow][tempCol] = 2
                    #  When change orange
                    result = True
                
                i += 1
            
            if (result) :
                time += 1
            
        
        i = 0
        while (i < n) :
            j = 0
            while (j < m) :
                if (mat[i][j] == 1) :
                    #  In case when orange are not rot
                    return -1
                
                j += 1
            
            i += 1
        
        return time
    

def main() :
    t = Timing()
    mat1 = [
        [0, 1, 1, 2],
        [0, 1, 0, 0],
        [0, 0, 1, 0],
        [0, 1, 2, 0]
    ]
    mat2 = [
        [1, 0, 1, 0],
        [2, 0, 2, 1],
        [1, 0, 0, 0]
    ]
    mat3 = [
        [1, 0, 1],
        [0, 2, 0],
        [1, 0, 1]
    ]
    print("Result mat1 : ", t.minTimeToRot(mat1))
    print("Result mat2 : ", t.minTimeToRot(mat2))
    print("Result mat3 : ", t.minTimeToRot(mat3))

if __name__ == "__main__": main()

Output

Result mat1 :  3
Result mat2 :  1
Result mat3 :  -1
#    Ruby Program for
#    Minimum time required to rot all oranges
class Position 
	# Define the accessor and reader of class Position
	attr_reader :row, :col
	attr_accessor :row, :col
	def initialize(row, col) 
		self.row = row
		self.col = col
	end
end

class Timing 
	def minTimeToRot(mat) 
		#  Number of row
		n = mat.length
		#  Number of columns
		m = mat[0].length

		record = []
		#  Define some auxliary variables
		size = 0
		times = 0
		tempRow = 0
		tempCol = 0
		result = true
		i = 0
		#  Add cordinate of rot oranges
		while (i < n) 
			j = 0
			while (j < m) 
				if (mat[i][j] == 2) 
					record.push(Position.new(i, j))
				end

				j += 1
			end

			i += 1
		end

		#  Execute this loop unit when record not empty and result is true
		while ((record.length > 0) && result == true) 
			#  Get the size of record
			size = record.length

			#  Change result
			result = false
			i = 0
			#  Check of all 4 Direction of rot orange
			#  Note size is based on record size
			while (i < size && record.length > 0) 
				#  Get record element
				curr = record.first()
				x = curr.row
				y = curr.col
				#  Remove record element
				record = record.drop(1)
				#  Up element adjustment 
				#  Get the position of row and columns
				tempRow = x - 1
				tempCol = y
				if ((tempRow >= 0 && tempRow < n)  && 
                    (tempCol >= 0 && tempCol < m) && 
                    (mat[tempRow][tempCol] == 1)) 
					#  Add change coordinate
					record.push(Position.new(tempRow, tempCol))
					#  Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2
					#  When change orange
					result = true
				end

				#  Change row
				tempRow = x + 1
				tempCol = y
				#  Down element adjustment 
				if ((tempRow >= 0 && tempRow < n) &&  
                    (tempCol >= 0 && tempCol < m) && 
                    (mat[tempRow][tempCol] == 1) ) 
					#  Change right orange
					#  Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2
					#  Add change cordinate
					record.push(Position.new(tempRow, tempCol))
					#  When change orange
					result = true
				end

				#  Change columns
				tempRow = x
				tempCol = y + 1
				#  Right element adjustment 
				if ((tempRow >= 0 && tempRow < n) &&  
                    (tempCol >= 0 && tempCol < m) && 
                    (mat[tempRow][tempCol] == 1) ) 
					#  Add change coordinate
					record.push(Position.new(tempRow, tempCol))
					#  Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2
					#  When change orange
					result = true
				end

				#  Change row
				tempRow = x
				#  Change columns
				tempCol = y - 1
				#  Left element
				if ((tempRow >= 0 && tempRow < n) && 
                    (mat[tempRow][tempCol] == 1) && 
                    (tempCol >= 0 && tempCol < m) ) 
					#  Add change coordinate
					record.push(Position.new(tempRow, tempCol))
					#  change orange 1 to 2
					#  Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2
					#  When change orange
					result = true
				end

				i += 1
			end

			if (result) 
				times = times + 1
			end

		end

		i = 0
		while (i < n) 
			j = 0
			while (j < m) 
				if (mat[i][j] == 1) 
					#  In case when orange are not rot
					return -1
				end

				j += 1
			end

			i += 1
		end

		return times
	end

end

def main() 
	t = Timing.new()
	mat1 = [
		[0, 1, 1, 2],
		[0, 1, 0, 0],
		[0, 0, 1, 0],
		[0, 1, 2, 0]
	]
	mat2 = [
		[1, 0, 1, 0],
		[2, 0, 2, 1],
		[1, 0, 0, 0]
	]
	mat3 = [
		[1, 0, 1],
		[0, 2, 0],
		[1, 0, 1]
	]
	print("Result mat1 : ", t.minTimeToRot(mat1), "\n")
	print("Result mat2 : ", t.minTimeToRot(mat2), "\n")
	print("Result mat3 : ", t.minTimeToRot(mat3), "\n")
end

main()

Output

Result mat1 : 3
Result mat2 : 1
Result mat3 : -1

import scala.collection.mutable._;
/*
    Scala Program for
    Minimum time required to rot all oranges
*/
class Position(var row: Int,
	var col: Int)
{

}
class Timing()
{
	def minTimeToRot(mat: Array[Array[Int]]): Int = {
		// Number of row
		var n: Int = mat.length;
		// Number of columns
		var m: Int = mat(0).length;
		var queue: Queue[Position] = new Queue[Position]();
		// Define some auxliary variables
		var size: Int = 0;
		var time: Int = 0;
		var tempRow: Int = 0;
		var tempCol: Int = 0;
		var result: Boolean = true;
		var i: Int = 0;
		// Add cordinate of rot oranges
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				if (mat(i)(j) == 2)
				{
					queue.enqueue(new Position(i, j));
				}
				j += 1;
			}
			i += 1;
		}
		// Execute this loop unit when queue not empty and result is true
		while (!queue.isEmpty && result == true)
		{
			// Get the size of queue
			size = queue.size;
			// Change result
			result = false;
			i = 0;
			// Check of all 4 Direction of rot orange
			// Note size is based on queue size
			while (i < size)
			{
				// Get queue element
				var curr: Position = queue.front;
				// Remove queue element
				queue.dequeue;
				// Up element adjustment 
				// Get the position of row and columns
				tempRow = curr.row - 1;
				tempCol = curr.col;
				if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
				{
					// Add change coordinate
					queue.enqueue(new Position(tempRow, tempCol));
					// Fresh orange to rot orange  
					mat(tempRow)(tempCol) = 2;
					// When change orange
					result = true;
				}
				// Change row
				tempRow = curr.row + 1;
				tempCol = curr.col;
				// Down element adjustment 
				if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
				{
					// Change right orange
					// Fresh orange to rot orange  
					mat(tempRow)(tempCol) = 2;
					// Add change cordinate
					queue.enqueue(new Position(tempRow, tempCol));
					// When change orange
					result = true;
				}
				// Change columns
				tempRow = curr.row;
				tempCol = curr.col + 1;
				// Right element adjustment 
				if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
				{
					// Add change coordinate
					queue.enqueue(new Position(tempRow, tempCol));
					// Fresh orange to rot orange  
					mat(tempRow)(tempCol) = 2;
					// When change orange
					result = true;
				}
				// Change row
				tempRow = curr.row;
				// Change columns
				tempCol = curr.col - 1;
				// Left element
				if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
				{
					// Add change coordinate
					queue.enqueue(new Position(tempRow, tempCol));
					// change orange 1 to 2
					// Fresh orange to rot orange  
					mat(tempRow)(tempCol) = 2;
					// When change orange
					result = true;
				}
				i += 1;
			}
			if (result)
			{
				time += 1;
			}
		}
		i = 0;
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				if (mat(i)(j) == 1)
				{
					// In case when orange are not rot
					return -1;
				}
				j += 1;
			}
			i += 1;
		}
		return time;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var t: Timing = new Timing();
		var mat1: Array[Array[Int]] = Array(
          Array(0, 1, 1, 2), 
          Array(0, 1, 0, 0), 
          Array(0, 0, 1, 0), 
          Array(0, 1, 2, 0)
        );
		var mat2: Array[Array[Int]] = Array(
          Array(1, 0, 1, 0), 
          Array(2, 0, 2, 1), 
          Array(1, 0, 0, 0)
        );
		var mat3: Array[Array[Int]] = Array(
          Array(1, 0, 1), 
          Array(0, 2, 0), 
          Array(1, 0, 1)
        );
		println("Result mat1 : " + t.minTimeToRot(mat1));
		println("Result mat2 : " + t.minTimeToRot(mat2));
		println("Result mat3 : " + t.minTimeToRot(mat3));
	}
}

Output

Result mat1 : 3
Result mat2 : 1
Result mat3 : -1
import Foundation;
/*
    Swift 4 Program for
    Minimum time required to rot all oranges
*/
class Position
{
	var row: Int;
	var col: Int;
	init(_ row: Int, _ col: Int)
	{
		self.row = row;
		self.col = col;
	}
}
class Timing
{
	func minTimeToRot(_ mat: inout[[Int]]) -> Int
	{
		// Number of row
		let n: Int = mat.count;
		// Number of columns
		let m: Int = mat[0].count;
		var queue = [Position]();
		// Define some auxliary variables
		var size: Int = 0;
		var time: Int = 0;
		var tempRow: Int = 0;
		var tempCol: Int = 0;
		var result: Bool = true;
		var i: Int = 0;
		// Add cordinate of rot oranges
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				if (mat[i][j] == 2)
				{
					queue.append(Position(i, j));
				}
				j += 1;
			}
			i += 1;
		}
		// Execute this loop unit when queue not empty and result is true
		while ((queue.count > 0) && result == true)
		{
			// Get the size of queue
			size = queue.count;
			// Change result
			result = false;
			i  = 0;
			// Check of all 4 Direction of rot orange
			// Note size is based on queue size
			while (i < size)
			{
				// Get queue element
				let curr: Position = queue[0];
				// Remove queue element
				queue.removeFirst();
				// Up element adjustment 
				// Get the position of row and columns
				tempRow = curr.row - 1;
				tempCol = curr.col;
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
				{
					// Add change coordinate
					queue.append(Position(tempRow, tempCol));
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// When change orange
					result = true;
				}
				// Change row
				tempRow = curr.row + 1;
				tempCol = curr.col;
				// Down element adjustment 
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
				{
					// Change right orange
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// Add change cordinate
					queue.append(Position(tempRow, tempCol));
					// When change orange
					result = true;
				}
				// Change columns
				tempRow = curr.row;
				tempCol = curr.col + 1;
				// Right element adjustment 
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
				{
					// Add change coordinate
					queue.append(Position(tempRow, tempCol));
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// When change orange
					result = true;
				}
				// Change row
				tempRow = curr.row;
				// Change columns
				tempCol = curr.col - 1;
				// Left element
				if ((tempRow >= 0 && tempRow < n) 
                    && (tempCol >= 0 && tempCol < m) 
                    && mat[tempRow][tempCol] == 1)
				{
					// Add change coordinate
					queue.append(Position(tempRow, tempCol));
					// change orange 1 to 2
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// When change orange
					result = true;
				}
				i += 1;
			}
			if (result)
			{
				time += 1;
			}
		}
		i = 0;
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				if (mat[i][j] == 1)
				{
					// In case when orange are not rot
					return -1;
				}
				j += 1;
			}
			i += 1;
		}
		return time;
	}
}
func main()
{
	let t: Timing = Timing();
	var mat1: [
		[Int]
	] = [
		[0, 1, 1, 2],
		[0, 1, 0, 0],
		[0, 0, 1, 0],
		[0, 1, 2, 0]
	];
	var mat2: [
		[Int]
	] = [
		[1, 0, 1, 0],
		[2, 0, 2, 1],
		[1, 0, 0, 0]
	];
	var mat3: [
		[Int]
	] = [
		[1, 0, 1],
		[0, 2, 0],
		[1, 0, 1]
	];
	print("Result mat1 : ", t.minTimeToRot(&mat1));
	print("Result mat2 : ", t.minTimeToRot(&mat2));
	print("Result mat3 : ", t.minTimeToRot(&mat3));
}
main();

Output

Result mat1 :  3
Result mat2 :  1
Result mat3 :  -1
/*
    Kotlin Program for
    Minimum time required to rot all oranges
*/
import java.util.Queue
import java.util.LinkedList
class Position
{
	var row: Int;
	var col: Int;
	constructor(row: Int, col: Int)
	{
		this.row = row;
		this.col = col;
	}
}
class Timing
{
	fun minTimeToRot(mat: Array < Array < Int >> ): Int
	{
		// Number of row
		val n: Int = mat.count();
		// Number of columns
		val m: Int = mat[0].count();
		var queue: Queue < Position > = LinkedList < Position > ();
		// Define some auxliary variables
		var size: Int ;
		var time: Int = 0;
		var tempRow: Int;
		var tempCol: Int ;
		var result: Boolean = true;
		var i: Int = 0;
		// Add cordinate of rot oranges
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				if (mat[i][j] == 2)
				{
					queue.add(Position(i, j));
				}
				j += 1;
			}
			i += 1;
		}
		// Execute this loop unit when queue not empty and result is true
		while (!queue.isEmpty() && result == true)
		{
			// Get the size of queue
			size = queue.size;
			// Change result
			result = false;
			i = 0;
			// Check of all 4 Direction of rot orange
			// Note size is based on queue size
			while (i < size)
			{
				// Get queue element
				val curr: Position = queue.peek();
				// Remove queue element
				queue.remove();
				// Up element adjustment 
				// Get the position of row and columns
				tempRow = curr.row - 1;
				tempCol = curr.col;
				if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
				{
					// Add change coordinate
					queue.add(Position(tempRow, tempCol));
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// When change orange
					result = true;
				}
				// Change row
				tempRow = curr.row + 1;
				tempCol = curr.col;
				// Down element adjustment 
				if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
				{
					// Change right orange
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// Add change cordinate
					queue.add(Position(tempRow, tempCol));
					// When change orange
					result = true;
				}
				// Change columns
				tempRow = curr.row;
				tempCol = curr.col + 1;
				// Right element adjustment 
				if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
				{
					// Add change coordinate
					queue.add(Position(tempRow, tempCol));
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// When change orange
					result = true;
				}
				// Change row
				tempRow = curr.row;
				// Change columns
				tempCol = curr.col - 1;
				// Left element
				if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
				{
					// Add change coordinate
					queue.add(Position(tempRow, tempCol));
					// change orange 1 to 2
					// Fresh orange to rot orange  
					mat[tempRow][tempCol] = 2;
					// When change orange
					result = true;
				}
				i += 1;
			}
			if (result)
			{
				time += 1;
			}
		}
		i = 0;
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				if (mat[i][j] == 1)
				{
					// In case when orange are not rot
					return -1;
				}
				j += 1;
			}
			i += 1;
		}
		return time;
	}
}
fun main(args: Array < String > ): Unit
{
	val t: Timing = Timing();
	val mat1: Array < Array < Int >> = arrayOf(arrayOf(0, 1, 1, 2), arrayOf(0, 1, 0, 0), arrayOf(0, 0, 1, 0), arrayOf(0, 1, 2, 0));
	val mat2: Array < Array < Int >> = arrayOf(arrayOf(1, 0, 1, 0), arrayOf(2, 0, 2, 1), arrayOf(1, 0, 0, 0));
	val mat3: Array < Array < Int >> = arrayOf(arrayOf(1, 0, 1), arrayOf(0, 2, 0), arrayOf(1, 0, 1));
	println("Result mat1 : " + t.minTimeToRot(mat1));
	println("Result mat2 : " + t.minTimeToRot(mat2));
	println("Result mat3 : " + t.minTimeToRot(mat3));
}

Output

Result mat1 : 3
Result mat2 : 1
Result mat3 : -1
package main
import "fmt"
/*
    Go Program for
    Minimum time required to rot all oranges
*/
type Position struct {
	row int
	col int
}
func getPosition(row int, col int) * Position {
	var me * Position = & Position {}
	me.row = row
	me.col = col
	return me
}
type Timing struct {}
func getTiming() * Timing {
	var me * Timing = & Timing {}
	return me
}
func(this Timing) minTimeToRot(mat[][] int) int {
	// Number of row
	var n int = len(mat)
	// Number of columns
	var m int = len(mat[0])
	var queue[] * Position
	// Define some auxliary variables
	var size int = 0
	var time int = 0
	var tempRow int = 0
	var tempCol int = 0
	var result bool = true
	// Add cordinate of rot oranges
	for i:= 0; i < n; i++{
		for j:= 0;j < m;j++{
			if mat[i][j] == 2 {
				queue = append(queue, getPosition(i, j))
			}
		}
	}
	// Execute this loop unit when queue not empty and result is true
	for ((len(queue) > 0) && result == true) {
		// Get the size of queue
		size = len(queue)
		// Change result
		result = false
		// Check of all 4 Direction of rot orange
		// Note size is based on queue size
		for i:= 0 ; i < size; i++{
			// Get queue element
			var curr * Position = queue[0]
			// Remove queue element
			queue = queue[1: ]
			// Up element adjustment 
			// Get the position of row and columns
			tempRow = curr.row - 1
			tempCol = curr.col
			if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
				// Add change coordinate
				queue = append(queue, getPosition(tempRow, tempCol))
				// Fresh orange to rot orange  
				mat[tempRow][tempCol] = 2
				// When change orange
				result = true
			}
			// Change row
			tempRow = curr.row + 1
			tempCol = curr.col
			// Down element adjustment 
			if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
				// Change right orange
				// Fresh orange to rot orange  
				mat[tempRow][tempCol] = 2
				// Add change cordinate
				queue = append(queue, getPosition(tempRow, tempCol))
				// When change orange
				result = true
			}
			// Change columns
			tempRow = curr.row
			tempCol = curr.col + 1
			// Right element adjustment 
			if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
				// Add change coordinate
				queue = append(queue, getPosition(tempRow, tempCol))
				// Fresh orange to rot orange  
				mat[tempRow][tempCol] = 2
				// When change orange
				result = true
			}
			// Change row
			tempRow = curr.row
			// Change columns
			tempCol = curr.col - 1
			// Left element
			if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
				// Add change coordinate
				queue = append(queue, getPosition(tempRow, tempCol))
				// change orange 1 to 2
				// Fresh orange to rot orange  
				mat[tempRow][tempCol] = 2
				// When change orange
				result = true
			}
		}
		if result {
			time++
		}
	}
	for i:= 0; i < n; i++{
		for j:= 0; j < m; j++{
			if mat[i][j] == 1 {
				// In case when orange are not rot
				return -1
			}
		}
	}
	return time
}
func main() {
	var t * Timing = getTiming()
	var mat1 = [][] int {
		{
			0,
			1,
			1,
			2,
		}, {
			0,
			1,
			0,
			0,
		}, {
			0,
			0,
			1,
			0,
		}, {
			0,
			1,
			2,
			0,
		},
	}
	var mat2 = [][] int {
		{
			1,
			0,
			1,
			0,
		}, {
			2,
			0,
			2,
			1,
		}, {
			1,
			0,
			0,
			0,
		},
	}
	var mat3 = [][] int {
		{
			1,
			0,
			1,
		}, {
			0,
			2,
			0,
		}, {
			1,
			0,
			1,
		},
	}
	fmt.Println("Result mat1 : ", t.minTimeToRot(mat1))
	fmt.Println("Result mat2 : ", t.minTimeToRot(mat2))
	fmt.Println("Result mat3 : ", t.minTimeToRot(mat3))
}

Output

Result mat1 : 3
Result mat2 : 1
Result mat3 : -1
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment