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
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