Maximum time required for all patients to get infected | C ++ program for the above approach ; Direction arrays ; Function to find the maximum time required for all patients to get infected ; Stores the number of rows ; Stores the number of columns ; Stores whether particular index ( i , j ) is visited or not ; Stores index and time of infection of infected persons ; Stores uninfected patients count ; Stores time at which last person got infected ; Traverse the matrix ; If the current patient is already infected ; Push the index of current patient and mark it as visited ; If current patient is uninfected increment uninfected count ; Iterate until queue becomes empty ; Stores the front element of queue ; Pop out the front element ; Check for all four adjacent indices ; Find the index of the adjacent cell ; If the current adjacent cell is invalid or it contains an infected patient ; Continue to the next neighbouring cell ; Push the infected neighbour into queue ; If an uninfected patient is present ; Return the final result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < pair < int , int > > direction = { { 1 , 0 } , { 0 , -1 } , { -1 , 0 } , { 0 , 1 } } ; int maximumTime ( vector < vector < int > > arr ) { int n = arr . size ( ) ; int m = arr [ 0 ] . size ( ) ; vector < vector < bool > > visited ( n , vector < bool > ( m , 0 ) ) ; queue < pair < pair < int , int > , int > > q ; int uninfected_count = 0 ; int time = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( arr [ i ] [ j ] == 2 ) { q . push ( { { i , j } , 0 } ) ; visited [ i ] [ j ] = 1 ; } if ( arr [ i ] [ j ] == 1 ) { uninfected_count ++ ; } } } while ( ! q . empty ( ) ) { pair < pair < int , int > , int > current = q . front ( ) ; time = current . second ; q . pop ( ) ; for ( auto it : direction ) { int i = current . first . first + it . first ; int j = current . first . second + it . second ; if ( i < 0 j < 0 i > = n j > = m arr [ i ] [ j ] != 1 visited [ i ] [ j ] != 0 ) { continue ; } q . push ( { { i , j } , time + 1 } ) ; visited [ i ] [ j ] = 1 ; uninfected_count -- ; } } if ( uninfected_count != 0 ) return -1 ; return time ; } int main ( ) { vector < vector < int > > arr = { { 2 , 1 , 0 , 2 , 1 } , { 1 , 0 , 1 , 2 , 1 } , { 1 , 0 , 0 , 2 , 1 } } ; cout << maximumTime ( arr ) ; return 0 ; }