{"id":"4ea6fa71-e097-421f-a744-48ce0ecaf609","name":"Rotting Oranges","description":"You are given an m * n matrix containing 0, 1 or 2 , where 0 represents an empty cell, 1 represents a fresh orange, 2 represents rotten orange. Every hour, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.\r\nPrint the minimum number of hours that must elapse until no cell has a fresh orange.","inputFormat":"First line contains two integers m and n.\r\nEach of next m line contains n integers 0,1 or 2.","outputFormat":"Print minimum hours.","constraints":"1 &lt;= m,n &lt;= 1000","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\ntypedef pair<int, int> pairs;\n\nint orangesRotting(vector<vector<int>>& grid){\n \n \n}\n\nint main(){\n \n int n,m;\n cin>>n>>m;\n \n vector<vector<int>>arr(n,vector<int>(m));\n \n for(int i=0;i<n;i++){\n for(int j=0;j<m;j++){\n int x;\n cin>>x;\n arr[i][j]=x;\n }\n }\n \n cout<<orangesRotting(arr);\n}"},"java":{"code":"import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.*;\n\nclass Main {\n\n public static void main(String[] args) throws NumberFormatException, IOException {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\n String[] st = br.readLine().split(\" \");\n int n = Integer.parseInt(st[0]);\n int m = Integer.parseInt(st[1]);\n\n int[][] arr = new int[n][m];\n\n for (int i = 0; i < n; i++) {\n st = br.readLine().split(\" \");\n for (int j = 0; j < m; j++) {\n arr[i][j] = Integer.parseInt(st[j]);\n }\n }\n\n System.out.println(orangesRotting(arr));\n\n }\n\n public static class Pair {\n int row;\n int col;\n\n Pair(int row, int col) {\n this.row = row;\n this.col = col;\n }\n\n }\n\n public static int orangesRotting(int[][] grid) {\n \n}\n \n \n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3 3\r\n2 1 1\r\n1 1 0\r\n0 1 1","sampleOutput":"4\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"788142ff-7bb4-429f-8dbc-55b922139dc8","name":"Rotting Oranges","slug":"rotting-oranges","type":1}],"next":{"id":"63399e1d-d9fb-4ca0-9a23-37479ce7d61a","name":"Rotting Oranges","type":0,"slug":"rotting-oranges"},"prev":{"id":"0adf902c-88c9-4310-8e9d-2afbe6c6ea47","name":"Number-of-distinct-island","type":3,"slug":"number-of-distinct-island"}}}

Rotting Oranges

You are given an m * n matrix containing 0, 1 or 2 , where 0 represents an empty cell, 1 represents a fresh orange, 2 represents rotten orange. Every hour, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Print the minimum number of hours that must elapse until no cell has a fresh orange.

{"id":"4ea6fa71-e097-421f-a744-48ce0ecaf609","name":"Rotting Oranges","description":"You are given an m * n matrix containing 0, 1 or 2 , where 0 represents an empty cell, 1 represents a fresh orange, 2 represents rotten orange. Every hour, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.\r\nPrint the minimum number of hours that must elapse until no cell has a fresh orange.","inputFormat":"First line contains two integers m and n.\r\nEach of next m line contains n integers 0,1 or 2.","outputFormat":"Print minimum hours.","constraints":"1 &lt;= m,n &lt;= 1000","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\ntypedef pair<int, int> pairs;\n\nint orangesRotting(vector<vector<int>>& grid){\n \n \n}\n\nint main(){\n \n int n,m;\n cin>>n>>m;\n \n vector<vector<int>>arr(n,vector<int>(m));\n \n for(int i=0;i<n;i++){\n for(int j=0;j<m;j++){\n int x;\n cin>>x;\n arr[i][j]=x;\n }\n }\n \n cout<<orangesRotting(arr);\n}"},"java":{"code":"import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.*;\n\nclass Main {\n\n public static void main(String[] args) throws NumberFormatException, IOException {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\n String[] st = br.readLine().split(\" \");\n int n = Integer.parseInt(st[0]);\n int m = Integer.parseInt(st[1]);\n\n int[][] arr = new int[n][m];\n\n for (int i = 0; i < n; i++) {\n st = br.readLine().split(\" \");\n for (int j = 0; j < m; j++) {\n arr[i][j] = Integer.parseInt(st[j]);\n }\n }\n\n System.out.println(orangesRotting(arr));\n\n }\n\n public static class Pair {\n int row;\n int col;\n\n Pair(int row, int col) {\n this.row = row;\n this.col = col;\n }\n\n }\n\n public static int orangesRotting(int[][] grid) {\n \n}\n \n \n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3 3\r\n2 1 1\r\n1 1 0\r\n0 1 1","sampleOutput":"4\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"788142ff-7bb4-429f-8dbc-55b922139dc8","name":"Rotting Oranges","slug":"rotting-oranges","type":1}],"next":{"id":"63399e1d-d9fb-4ca0-9a23-37479ce7d61a","name":"Rotting Oranges","type":0,"slug":"rotting-oranges"},"prev":{"id":"0adf902c-88c9-4310-8e9d-2afbe6c6ea47","name":"Number-of-distinct-island","type":3,"slug":"number-of-distinct-island"}}}
plane

Editor

Loading...

Rotting Oranges

easy

You are given an m * n matrix containing 0, 1 or 2 , where 0 represents an empty cell, 1 represents a fresh orange, 2 represents rotten orange. Every hour, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Print the minimum number of hours that must elapse until no cell has a fresh orange.

Constraints

1 <= m,n <= 1000

Format

Input

First line contains two integers m and n. Each of next m line contains n integers 0,1 or 2.

Output

Print minimum hours.

Example

Sample Input

3 3 2 1 1 1 1 0 0 1 1

Sample Output

4

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode