Maximum of all distances to the nearest 1 cell from any 0 cell in a Binary matrix | C ++ Program to find the maximum distance from a 0 - cell to a 1 - cell ; Function to find the maximum distance ; Set up top row and left column ; Pass one : top left to bottom right ; Check if there was no " One " Cell ; Set up top row and left column ; Past two : bottom right to top left ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxDistance ( vector < vector < int > > & grid ) { if ( ! grid . size ( ) ) return -1 ; int N = grid . size ( ) ; int INF = 1000000 ; vector < vector < int > > dp ( N , vector < int > ( N , 0 ) ) ; grid [ 0 ] [ 0 ] = grid [ 0 ] [ 0 ] == 1 ? 0 : INF ; for ( int i = 1 ; i < N ; i ++ ) grid [ 0 ] [ i ] = grid [ 0 ] [ i ] == 1 ? 0 : grid [ 0 ] [ i - 1 ] + 1 ; for ( int i = 1 ; i < N ; i ++ ) grid [ i ] [ 0 ] = grid [ i ] [ 0 ] == 1 ? 0 : grid [ i - 1 ] [ 0 ] + 1 ; for ( int i = 1 ; i < N ; i ++ ) { for ( int j = 1 ; j < N ; j ++ ) { grid [ i ] [ j ] = grid [ i ] [ j ] == 1 ? 0 : min ( grid [ i - 1 ] [ j ] , grid [ i ] [ j - 1 ] ) + 1 ; } } if ( grid [ N - 1 ] [ N - 1 ] >= INF ) return -1 ; int maxi = grid [ N - 1 ] [ N - 1 ] ; for ( int i = N - 2 ; i >= 0 ; i -- ) { grid [ N - 1 ] [ i ] = min ( grid [ N - 1 ] [ i ] , grid [ N - 1 ] [ i + 1 ] + 1 ) ; maxi = max ( grid [ N - 1 ] [ i ] , maxi ) ; } for ( int i = N - 2 ; i >= 0 ; i -- ) { grid [ i ] [ N - 1 ] = min ( grid [ i ] [ N - 1 ] , grid [ i + 1 ] [ N - 1 ] + 1 ) ; maxi = max ( grid [ i ] [ N - 1 ] , maxi ) ; } for ( int i = N - 2 ; i >= 0 ; i -- ) { for ( int j = N - 2 ; j >= 0 ; j -- ) { grid [ i ] [ j ] = min ( grid [ i ] [ j ] , min ( grid [ i + 1 ] [ j ] + 1 , grid [ i ] [ j + 1 ] + 1 ) ) ; maxi = max ( grid [ i ] [ j ] , maxi ) ; } } return ! maxi ? -1 : maxi ; } int main ( ) { vector < vector < int > > arr = { { 0 , 0 , 1 } , { 0 , 0 , 0 } , { 0 , 0 , 0 } } ; cout << maxDistance ( arr ) << endl ; return 0 ; }