Travel diaries
Practice
3.1 (34 votes)
Algorithms
Breadth first search
Grammar Verified
Graphs
Medium
Queue
Problem
86% Success 5871 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

You are given a matrix of size N×M that contains the digits 0, 1, or 2 only. All the cells that contain 1 and are adjacent to any cell that contains 2 will be converted from 1 to 2, simultaneously in 1 second. Write a program to find the minimum time to convert all the cells having value 1 to 2.

Input format

  • First line: Two space-separated integers N and M
  • Next N lines: M space-separated integers (denoting the matrix)

Output format

Print the minimum time to convert all the cells having value 1 to 2.

Constraints

1≤N,M≤103

Sample Input
3 5
2 1 0 2 1
1 0 1 2 1
1 0 0 2 1
Sample Output
2
Explanation

If you starts from the cell [1,4] or [3,4] and travels to [2,3] then the cost will be 2 which is maximum of all possible journeys.

Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Submissions
Please login to view your submissions
Similar Problems
1.Matrix
Points:30
14 votes
Tags:
AlgorithmsBreadth First SearchGraphsMedium
2.Big P and Party
Points:30
18 votes
Tags:
AlgorithmsApprovedBreadth First SearchGraphsMediumOpen
3.Permutation Swaps
Points:30
90 votes
Tags:
AlgorithmsApprovedBreadth First SearchDepth First SearchGraphsMediumReady
Editorial

Login to unlock the editorial