How long before the virus spreads?


  • 1
    A

    You are given a matrix filled with 0s and 1s. Assume, 0s represent water-bodies and 1s represent the cities. You're also given the coordinates of a virus within the matrix. The virus can only contaminate the city and NOT the water bodies. Also the virus can only spread horizontally and vertically but NOT diagonally. Given that a virus can spread to its immediate horizontal and vertical neighbours in 1 second, how long (in seconds) will it take for the virus to contaminate all the cities? The cities are placed in the matrix such that they are not isolated by water bodies, to be clear, there are no islands in the map (every city in the map is reachable by the virus).

    0_1467728915908_leet (1).jpg

    Examples:
    Example 1 should return 4.
    Example 2 should return 6.


  • 0

    If I understand the question correctly, we just have to do a BFS from the given start point of the virus, then count the total levels of the BFS, and that will be the answer.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.