Check if there are T number of continuous of blocks of 0 s or not in given Binary Matrix | python 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
import math NEW_LINE M = 1000000000 + 7 NEW_LINE directions = [ [ 0 , 1 ] , [ - 1 , 0 ] , [ 0 , - 1 ] , [ 1 , 0 ] , [ 1 , 1 ] , [ - 1 , - 1 ] , [ - 1 , 1 ] , [ 1 , - 1 ] ] NEW_LINE def isInside ( i , j , N , M ) : NEW_LINE INDENT if ( i >= 0 and i < N and j >= 0 and j < M ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def DFS ( mat , N , M , i , j , visited ) : NEW_LINE INDENT if ( visited [ i ] [ j ] == True ) : NEW_LINE INDENT return NEW_LINE DEDENT visited [ i ] [ j ] = True NEW_LINE for it in directions : NEW_LINE INDENT I = i + it [ 0 ] NEW_LINE J = j + it [ 1 ] NEW_LINE if ( isInside ( I , J , N , M ) ) : NEW_LINE INDENT if ( mat [ I ] [ J ] == 0 ) : NEW_LINE INDENT DFS ( mat , N , M , I , J , visited ) NEW_LINE DEDENT DEDENT DEDENT DEDENT def check ( N , M , mat ) : NEW_LINE INDENT black = 0 NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT for j in range ( 0 , M ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == 0 ) : NEW_LINE INDENT black += 1 NEW_LINE DEDENT DEDENT DEDENT if ( black < 2 * ( max ( N , M ) ) ) : NEW_LINE INDENT print ( " NO " ) NEW_LINE return NEW_LINE DEDENT visited = [ ] NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT temp = [ ] NEW_LINE for j in range ( 0 , M ) : NEW_LINE INDENT temp . append ( False ) NEW_LINE DEDENT visited . append ( temp ) NEW_LINE DEDENT black_spots = 0 NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT for j in range ( 0 , M ) : NEW_LINE INDENT if ( visited [ i ] [ j ] == False and mat [ i ] [ j ] == 0 ) : NEW_LINE INDENT black_spots += 1 NEW_LINE DFS ( mat , N , M , i , j , visited ) NEW_LINE DEDENT DEDENT DEDENT T = math . gcd ( N , M ) NEW_LINE if black_spots >= T : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 3 NEW_LINE M = 3 NEW_LINE mat = [ [ 0 , 0 , 1 ] , [ 1 , 1 , 1 ] , [ 0 , 0 , 1 ] ] NEW_LINE check ( M , N , mat ) NEW_LINE DEDENT