Given a binary matrix mat[][] of dimensions M*N, the task is to check whether there exist T continuous blocks of 0s or not and at least 2*max(M, N) cells with value 0s or not. If found to be true, then print Yes. Otherwise, print No.
T is defined as the GCD of N and M. A continuous block is defined as the continuous stretch through row-wise or columns-wise or diagonal-wise.
Examples:
Input: N = 3, M = 4, mat[][] = { {1, 0, 0}, {1, 1, 0}, {0, 0, 0}, {0, 0, 1}}
Output: Yes
Explanation: Matrix has exactly 8 cells with value 0 which is equal to 2*max(N, M )) and there is 1 continuous spot which is equal to GCD of N and M.Input: N = 3, M = 3, mat[][] = {{0, 0, 1}, {1, 1, 1}, {0, 0, 1}}
Output: No
Approach: The idea is to count the number of cells with value 0 and if that satisfies the condition then find the greatest common divisor of M and N and perform a depth-first search to find the number of connected components with value 0. Follow the steps below to solve the problem:
- Initialize a variable, say black as 0 and count the number of cells with value 0.
- If black is less than equal to 2*max(M, N) then print No and return from the function.
- Initialize a variable, say blackSpots as 0 to count the number of continuous spots.
- Iterate over the range [0, M) using the variable i and nested iterate over the range [0, N) using the variable j and if the current cell visited[i][j] as false and if mat[i][j] is 0 then perform the DFS Traversal on given matrix with current cell to find the continuous segment with value 0 row-wise, column-wise and diagonal-wise and increase the value of blackSpots by 1.
- After performing the above steps, if the value of blackSpots is greater than gcd(M, N), then print Yes. Otherwise, print No.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const long long M = 1e9 + 7;// Stores the moves in the matrixvector<pair<int, int> > directions = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 }, { 1, 1 }, { -1, -1 }, { -1, 1 }, { 1, -1 } };// Function to find if the current cell// lies in the matrix or notbool isInside(int i, int j, int N, int M){ if (i >= 0 && i < N && j >= 0 && j < M) { return true; } return false;}// Function to perform the DFS Traversalvoid 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; // Iterate over the direction vector 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 Call DFS(mat, N, M, I, J, visited); } } }}// Function to check if it satisfy the// given criteria or notvoid check(int N, int M, vector<vector<int> >& mat){ // Keeps the count of cell having // value as 0 int black = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (mat[i][j] == 0) { black++; } } } // If condition doesn't satisfy 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); } // Keeps the track of unvisited cell // having values 0 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) { // Increasing count of // black_spot black_spots++; DFS(mat, N, M, i, j, visited); } } } // Find the GCD of N and M int T = __gcd(N, M); // Print the result cout << (black_spots >= T ? "Yes" : "No");}// Driver Codeint 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;} |
Java
import java.util.ArrayList;import java.util.List;class Pair { int first, second; Pair(int first, int second) { this.first = first; this.second = second; }}public class Main { static final int M = (int)1e9 + 7; // Stores the moves in the matrix static List<Pair> directions = new ArrayList<Pair>() { { add(new Pair(0, 1)); add(new Pair(-1, 0)); add(new Pair(0, -1)); add(new Pair(1, 0)); add(new Pair(1, 1)); add(new Pair(-1, -1)); add(new Pair(-1, 1)); add(new Pair(1, -1)); } }; // Function to find if the current cell // lies in the matrix or not static boolean isInside(int i, int j, int N, int M) { if (i >= 0 && i < N && j >= 0 && j < M) { return true; } return false; } // gcd() method, returns the GCD of a and b static int gcd(int a, int b) { // stores minimum(a, b) int i; if (a < b) i = a; else i = b; // take a loop iterating through smaller number to 1 for (i = i; i > 1; i--) { // check if the current value of i divides both // numbers with remainder 0 if yes, then i is // the GCD of a and b if (a % i == 0 && b % i == 0) return i; } // if there are no common factors for a and b other // than 1, then GCD of a and b is 1 return 1; } // Function to perform the DFS Traversal static void DFS(int[][] mat, int N, int M, int i, int j, boolean[][] visited) { if (visited[i][j] == true) { return; } visited[i][j] = true; // Iterate over the direction vector for (Pair pair : directions) { int I = i + pair.first; int J = j + pair.second; if (isInside(I, J, N, M)) { if (mat[I][J] == 0) { // DFS Call DFS(mat, N, M, I, J, visited); } } } } // Function to check if it satisfy the // given criteria or not static void check(int N, int M, int[][] mat) { // Keeps the count of cell having // value as 0 int black = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (mat[i][j] == 0) { black++; } } } // If condition doesn't satisfy if (black < 2 * (Math.max(N, M))) { System.out.println("NO"); return; } boolean[][] visited = new boolean[N][M]; // Keeps the track of unvisited cell // having values 0 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) { // Increasing count of // black_spot black_spots++; DFS(mat, N, M, i, j, visited); } } } // Find the GCD of N and M int T = gcd(N, M); // Print the result System.out.println(black_spots >= T ? "Yes" : "No"); } // Driver Code public static void main(String[] args) { int N = 3, M = 3; int[][] mat = { { 0, 0, 1 }, { 1, 1, 1 }, { 0, 0, 1 } }; check(M, N, mat); }}// This code is contributed by lokeshpotta20. |
Python3
# python program for the above approachimport mathM = 1000000000 + 7# Stores the moves in the matrixdirections = [[0, 1], [-1, 0], [0, -1], [1, 0], [1, 1], [-1, -1], [-1, 1], [1, -1]]# Function to find if the current cell# lies in the matrix or notdef isInside(i, j, N, M): if (i >= 0 and i < N and j >= 0 and j < M): return True return False# Function to perform the DFS Traversaldef DFS(mat, N, M, i, j, visited): if (visited[i][j] == True): return visited[i][j] = True # Iterate over the direction vector for it in directions: I = i + it[0] J = j + it[1] if (isInside(I, J, N, M)): if (mat[I][J] == 0): # DFS Call DFS(mat, N, M, I, J, visited)# Function to check if it satisfy the# given criteria or notdef check(N, M, mat): # Keeps the count of cell having # value as 0 black = 0 for i in range(0, N): for j in range(0, M): if (mat[i][j] == 0): black += 1 # If condition doesn't satisfy if (black < 2 * (max(N, M))): print("NO") return visited = [] for i in range(0, N): temp = [] for j in range(0, M): temp.append(False) visited.append(temp) # Keeps the track of unvisited cell # having values 0 black_spots = 0 for i in range(0, N): for j in range(0, M): if (visited[i][j] == False and mat[i][j] == 0): # Increasing count of # black_spot black_spots += 1 DFS(mat, N, M, i, j, visited) # Find the GCD of N and M T = math.gcd(N, M) # Print the result if black_spots >= T: print("Yes") else: print("No")# Driver Codeif __name__ == "__main__": N = 3 M = 3 mat = [[0, 0, 1], [1, 1, 1], [0, 0, 1]] check(M, N, mat) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;namespace CheckCriteria{ class Program { // Function to find GCD static int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); } static int M = (int)(1e9 + 7); // Stores the moves in the matrix static int[][] directions = new int[][] { new int[] { 0, 1 }, new int[] { -1, 0 }, new int[] { 0, -1 }, new int[] { 1, 0 }, new int[] { 1, 1 }, new int[] { -1, -1 }, new int[] { -1, 1 }, new int[] { 1, -1 } }; // Function to find if the current cell // lies in the matrix or not static bool IsInside(int i, int j, int N, int M) { if (i >= 0 && i < N && j >= 0 && j < M) { return true; } return false; } // C# code for DFS Traversal private static void DFS(int[][] mat, int N, int M, int i, int j, bool[][] visited) { if (visited[i][j] == true) { return; } visited[i][j] = true; // Iterate over the direction vector foreach (int[] it in directions) { int I = i + it[0]; int J = j + it[1]; if (IsInside(I, J, N, M)) { if (mat[I][J] == 0) { // DFS Call DFS(mat, N, M, I, J, visited); } } } } // Function to check if it satisfy the // given criteria or not static void Check(int N, int M, int[][] mat) { // Keeps the count of cell having // value as 0 int black = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (mat[i][j] == 0) { black++; } } } // If condition doesn't satisfy if (black < 2 * Math.Max(N, M)) { Console.WriteLine("NO"); return; } bool[][] visited = new bool[N][]; for (int i = 0; i < N; i++) { visited[i] = new bool[M]; for (int j = 0; j < M; j++) { visited[i][j] = false; } } // Keeps the track of unvisited cell // having values 0 int black_spots = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (!visited[i][j] && mat[i][j] == 0) { // Increasing count of // black_spot black_spots++; DFS(mat, N, M, i, j, visited); } } } // Find the GCD of N and M int T = GCD(N, M); // Print the result Console.WriteLine(black_spots >= T ? "Yes" : "No"); } // Driver Code static void Main(string[] args) { int N = 3; int M = 3; int[][] mat = { new int[] { 0, 0, 1 }, new int[] { 1, 1, 1 }, new int[] { 0, 0, 1 }, }; Check(N, M, mat); } }}// This code is contributed by prajwal kandekar |
Javascript
<script>// Javascript program for the above approachlet M = 1e9 + 7;// Stores the moves in the matrixlet directions = [ [0, 1], [-1, 0], [0, -1], [1, 0], [1, 1], [-1, -1], [-1, 1], [1, -1],];// Function to find if the current cell// lies in the matrix or notfunction isInside(i, j, N, M) { if (i >= 0 && i < N && j >= 0 && j < M) { return true; } return false;}// Function to perform the DFS Traversalfunction DFS(mat, N, M, i, j, visited) { if (visited[i][j] == true) { return; } visited[i][j] = true; // Iterate over the direction vector for (let it of directions) { let I = i + it[0]; let J = j + it[1]; if (isInside(I, J, N, M)) { if (mat[I][J] == 0) { // DFS Call DFS(mat, N, M, I, J, visited); } } }}// Function to check if it satisfy the// given criteria or notfunction check(N, M, mat) { // Keeps the count of cell having // value as 0 let black = 0; for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { if (mat[i][j] == 0) { black++; } } } // If condition doesn't satisfy if (black < 2 * Math.max(N, M)) { document.write("NO<br>"); return; } let visited = []; for (let i = 0; i < N; i++) { let temp = []; for (let j = 0; j < M; j++) { temp.push(false); } visited.push(temp); } // Keeps the track of unvisited cell // having values 0 let black_spots = 0; for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { if (visited[i][j] == false && mat[i][j] == 0) { // Increasing count of // black_spot black_spots++; DFS(mat, N, M, i, j, visited); } } } // Find the GCD of N and M let T = __gcd(N, M); // Print the result cout << (black_spots >= T ? "Yes" : "No");}// Driver Codelet N = 3;M = 3;let mat = [ [0, 0, 1], [1, 1, 1], [0, 0, 1],];check(M, N, mat);// This code is contributed by gfgking.</script> |
Output:
NO
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
