Check if there are T number of continuous of blocks of 0 s or not in given Binary Matrix | C ++ program for the above approach ; Stores the moves in the matrix ; Function to find if the current cell lies in the matrix or not ; Function to perform the DFS Traversal ; Iterate over the direction vector ; DFS Call ; Function to check if it satisfy the given criteria or not ; Keeps the count of cell having value as 0 ; If condition doesn 't satisfy ; Keeps the track of unvisted cell having values 0 ; Increasing count of black_spot ; Find the GCD of N and M ; Print the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const long long M = 1e9 + 7 ; vector < pair < int , int > > directions = { { 0 , 1 } , { -1 , 0 } , { 0 , -1 } , { 1 , 0 } , { 1 , 1 } , { -1 , -1 } , { -1 , 1 } , { 1 , -1 } } ; bool isInside ( int i , int j , int N , int M ) { if ( i >= 0 && i < N && j >= 0 && j < M ) { return true ; } return false ; } void DFS ( vector < vector < int > > mat , int N , int M , int i , int j , vector < vector < bool > > & visited ) { if ( visited [ i ] [ j ] == true ) { return ; } visited [ i ] [ j ] = true ; for ( auto it : directions ) { int I = i + it . first ; int J = j + it . second ; if ( isInside ( I , J , N , M ) ) { if ( mat [ I ] [ J ] == 0 ) { DFS ( mat , N , M , I , J , visited ) ; } } } } void check ( int N , int M , vector < vector < int > > & mat ) { int black = 0 ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { if ( mat [ i ] [ j ] == 0 ) { black ++ ; } } } if ( black < 2 * ( max ( N , M ) ) ) { cout << " NO " << endl ; return ; } vector < vector < bool > > visited ; for ( int i = 0 ; i < N ; i ++ ) { vector < bool > temp ; for ( int j = 0 ; j < M ; j ++ ) { temp . push_back ( false ) ; } visited . push_back ( temp ) ; } int black_spots = 0 ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { if ( visited [ i ] [ j ] == false && mat [ i ] [ j ] == 0 ) { black_spots ++ ; DFS ( mat , N , M , i , j , visited ) ; } } } int T = __gcd ( N , M ) ; cout << ( black_spots >= T ? " Yes " : " No " ) ; } int main ( ) { int N = 3 , M = 3 ; vector < vector < int > > mat = { { 0 , 0 , 1 } , { 1 , 1 , 1 } , { 0 , 0 , 1 } } ; check ( M , N , mat ) ; return 0 ; }