Given a matrix of size N * M and Q queries, the task is to find how many different regions will be there, after performing the queries. In each query:
- There are four integers x1, y1, x2, y2 denoting two cells of the matrix (x1, y1) and (x2, y2) which are adjacent to each other.
- Create a boundary along the common side of the cells.
Note: Two regions are different if there is no way from one region to another without crossing the boundary
Examples:
Input: N = 2, M = 2, Q = 2, queries = { {1, 1, 2, 1}, {2, 2, 1, 2} }
Output: 2
Explanation:
Example 1
See the above image for better understanding. Fig 1 shows matrix without any boundary
Fig 2 shows, matrix after the boundaries are formed between (1, 1), (2, 1) and (2, 2), (1, 2).
Two regions are created.Input: N = 2, M = 2, Q = 10,
queries = {{2, 1, 2, 2}, {1, 2, 2, 2}, {1, 3, 2, 3}, {1, 4, 2, 4}, {2, 3, 3, 3}, {3, 3, 3, 4}, {3, 3, 4, 3}, {3, 3, 3, 2}, {3, 1, 3, 2}, {4, 1, 4, 2}}Output: 2
Explanation: See the regions formed in the image provided belowExample 2
Approach: The problem can be solved by using hashing and DFS based on the following idea:
Create hash to store if the boundaries are formed vertically or horizontally and which cells have already taken part in the boundary forming operations.
Then visit the cells of the matrix using dfs and check the boundaries between them are forming a different region or not.
Follow the steps mentioned below to solve the problem:
- Create two hash tables, to store the status of lines present in vertically and horizontally adjacent cells.
- Create another hash table to store if a cell is visited or not.
- Start traversing the queries, and in each iteration:
- Check if the given two cells are vertically adjacent or horizontally.
- Mark the hash tables according to that to avoid considering them in the same region.
- Traverse the matrix, and in each iteration:
- Check if the current cell is visited or not.
- If it is not visited, increment the count of TotalRegion and then use DFS to recursively visit its adjacent cells (if no boundary between them) and mark all the cells in that region as visited.
- Return the count of TotalRegion in the matrix after performing
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Recursive function to traverse the matrixvoid traverse(int i, int j, int N, int M, vector<vector<bool> >& vis, vector<vector<bool> >& row, vector<vector<bool> >& col){ if (i <= 0 || i > N || j <= 0 || j > M || vis[i][j]) return; // Mark Current cell visited. vis[i][j] = true; // Traverse adjacent cells in all directions // (up, down, right, left) that // do not include lines between if (row[i][j]) traverse(i, j + 1, N, M, vis, row, col); if (col[i][j]) traverse(i + 1, j, N, M, vis, row, col); if (row[i][j - 1]) traverse(i, j - 1, N, M, vis, row, col); if (col[i - 1][j]) traverse(i - 1, j, N, M, vis, row, col);}// Function to count the total regionsint count(int N, int M, int K, vector<vector<int> >& q){ vector<vector<bool> > row(N + 1, vector<bool>( M + 1, true)); vector<vector<bool> > col(N + 1, vector<bool>( M + 1, true)); vector<vector<bool> > vis(N + 1, vector<bool>( M + 1, false)); for (int i = 0; i < K; i++) { // Hash array value set to false // if there is line between // two adjacent cell in same row // If query is {0 1 1 1} or // {1 1 0 1} we make row[0][1]= false, // that means there is vertical line // after the cell [0][1] if (q[i][0] == q[i][2]) { int mn = min(q[i][1], q[i][3]); row[q[i][0]][mn] = false; } // Hash array value set to false if // there is line between // two adjacent cell in same column // If query is {2 3 2 4} or {2 4 2 3} // we make col[2][3]= false, // that means there is horizontal line // below the cell [2][3] else { int mn = min(q[i][0], q[i][2]); col[mn][q[i][1]] = false; } } // Store count of total regions after // performing K queries. int TotalRegion = 0; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { // If current Cell // is not visited // then increment the TotalRegion // count and traverse // all the cell in that region if (!vis[i][j]) { TotalRegion++; traverse(i, j, N, M, vis, row, col); } } } return TotalRegion;}// Driver codeint main(){ vector<vector<int> > q; int N = 5, M = 5; int K = 10; q.push_back({ 2, 1, 2, 2 }); q.push_back({ 1, 2, 2, 2 }); q.push_back({ 1, 3, 2, 3 }); q.push_back({ 1, 4, 2, 4 }); q.push_back({ 2, 3, 3, 3 }); q.push_back({ 3, 3, 3, 4 }); q.push_back({ 3, 3, 4, 3 }); q.push_back({ 3, 3, 3, 2 }); q.push_back({ 3, 1, 3, 2 }); q.push_back({ 4, 1, 4, 2 }); cout << count(N, M, K, q); return 0;} |
Java
// Java program for above approachimport java.io.*;import java.util.*;import java.util.ArrayList;class GFG {// Recursive function to traverse the matrixstatic void traverse(int i, int j, int N, int M, boolean[][] vis, boolean[][] row, boolean[][] col){ if (i <= 0 || i > N || j <= 0 || j > M || vis[i][j]) return; // Mark Current cell visited. vis[i][j] = true; // Traverse adjacent cells in all directions // (up, down, right, left) that // do not include lines between if (row[i][j]) traverse(i, j + 1, N, M, vis, row, col); if (col[i][j]) traverse(i + 1, j, N, M, vis, row, col); if (row[i][j - 1]) traverse(i, j - 1, N, M, vis, row, col); if (col[i - 1][j]) traverse(i - 1, j, N, M, vis, row, col);} // Function to count the total regionsstatic int count(int N, int M, int K, ArrayList<ArrayList<Integer> > q){ boolean[][] row = new boolean[N+1][M+1]; boolean[][] col = new boolean[N+1][M+1]; boolean[][] vis = new boolean[N+1][M+1]; for(int i = 0; i < N+1; i++){ for(int j = 0; j < M+1; j++) { row[i][j]=true; col[i][j]=true; vis[i][j]=false; } } for (int i = 0; i < K; i++) { // Hash array value set to false // if there is line between // two adjacent cell in same row // If query is {0 1 1 1} or // {1 1 0 1} we make row[0][1]= false, // that means there is vertical line // after the cell [0][1] if (q.get(i).get(0) == q.get(i).get(2)) { int mn = Math.min(q.get(i).get(1), q.get(i).get(3)); row[q.get(i).get(0)][mn] = false; } // Hash array value set to false if // there is line between // two adjacent cell in same column // If query is {2 3 2 4} or {2 4 2 3} // we make col[2][3]= false, // that means there is horizontal line // below the cell [2][3] else { int mn = Math.min(q.get(i).get(0), q.get(i).get(2)); col[mn][q.get(i).get(1)] = false; } } // Store count of total regions after // performing K queries. int TotalRegion = 0; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { // If current Cell // is not visited // then increment the TotalRegion // count and traverse // all the cell in that region if (!vis[i][j]) { TotalRegion++; traverse(i, j, N, M, vis, row, col); } } } return TotalRegion;}// driver codepublic static void main(String[] args){ ArrayList<ArrayList<Integer> > q = new ArrayList<ArrayList<Integer> >(); int N = 5, M = 5; int K = 10; q.add(new ArrayList<Integer>(Arrays.asList(2, 1, 2, 2))); q.add(new ArrayList<Integer>(Arrays.asList(1, 2, 2, 2))); q.add(new ArrayList<Integer>(Arrays.asList(1, 3, 2, 3))); q.add(new ArrayList<Integer>(Arrays.asList(1, 4, 2, 4))); q.add(new ArrayList<Integer>(Arrays.asList(2, 3, 3, 3))); q.add(new ArrayList<Integer>(Arrays.asList(3, 3, 3, 4))); q.add(new ArrayList<Integer>(Arrays.asList(3, 3, 4, 3))); q.add(new ArrayList<Integer>(Arrays.asList(3, 3, 3, 2))); q.add(new ArrayList<Integer>(Arrays.asList(3, 1, 3, 2))); q.add(new ArrayList<Integer>(Arrays.asList(4, 1, 4, 2))); System.out.print(count(N, M, K, q));}}// This code is contributed by Pushpesh Raj |
Python3
# Python code to implement the approach# Recursive function to traverse the matrixdef traverse(i, j, N, M, vis, row, col): if (i <= 0 or i > N or j <= 0 or j > M or vis[i][j]): return # Mark Current cell visited. vis[i][j] = True # Traverse adjacent cells in all directions # (up, down, right, left) that # do not include lines between if (row[i][j]): traverse(i, j + 1, N, M,vis, row, col) if (col[i][j]): traverse(i + 1, j, N, M,vis, row, col) if (row[i][j - 1]): traverse(i, j - 1, N, M,vis, row, col) if (col[i - 1][j]): traverse(i - 1, j, N, M,vis, row, col)# Function to count the total regionsdef count(N, M, K, q): row = [[True for col in range(M+1)]for row in range(N+1)] col = [[True for col in range(M+1)]for row in range(N+1)] vis = [[False for col in range(M+1)]for row in range(N+1)] for i in range(K): # Hash array value set to false # if there is line between # two adjacent cell in same row # If query is {0 1 1 1} or # {1 1 0 1} we make row[0][1]= false, # that means there is vertical line # after the cell [0][1] if (q[i][0] == q[i][2]): mn = min(q[i][1], q[i][3]) row[q[i][0]][mn] = False # Hash array value set to false if # there is line between # two adjacent cell in same column # If query is {2 3 2 4} or {2 4 2 3} # we make col[2][3]= false, # that means there is horizontal line # below the cell [2][3] else: mn = min(q[i][0], q[i][2]) col[mn][q[i][1]] = False # Store count of total regions after # performing K queries. TotalRegion = 0 for i in range(1,N+1): for j in range(1,M+1): # If current Cell # is not visited # then increment the TotalRegion # count and traverse # all the cell in that region if (vis[i][j] == False): TotalRegion += 1 traverse(i, j, N, M,vis, row, col) return TotalRegion# Driver codeq = []N = 5M = 5K = 10q.append([2, 1, 2, 2])q.append([1, 2, 2, 2])q.append([1, 3, 2, 3])q.append([1, 4, 2, 4])q.append([2, 3, 3, 3])q.append([3, 3, 3, 4])q.append([3, 3, 4, 3])q.append([3, 3, 3, 2])q.append([3, 1, 3, 2])q.append([4, 1, 4, 2])print(count(N, M, K, q))# This code is contributed by ShinjanPatra |
C#
// C# program for above approachusing System;public class GFG { // Recursive function to traverse the matrix static void traverse(int i, int j, int N, int M, bool[, ] vis, bool[, ] row, bool[, ] col) { if (i <= 0 || i > N || j <= 0 || j > M || vis[i, j]) return; // Mark Current cell visited. vis[i, j] = true; // Traverse adjacent cells in all directions // (up, down, right, left) that // do not include lines between if (row[i, j]) traverse(i, j + 1, N, M, vis, row, col); if (col[i, j]) traverse(i + 1, j, N, M, vis, row, col); if (row[i, j - 1]) traverse(i, j - 1, N, M, vis, row, col); if (col[i - 1, j]) traverse(i - 1, j, N, M, vis, row, col); } // Function to count the total regions static int count(int N, int M, int K, int[, ] q) { bool[, ] row = new bool[N + 1, M + 1]; bool[, ] col = new bool[N + 1, M + 1]; bool[, ] vis = new bool[N + 1, M + 1]; for (int i = 0; i < N + 1; i++) { for (int j = 0; j < M + 1; j++) { row[i, j] = true; col[i, j] = true; vis[i, j] = false; } } for (int i = 0; i < K; i++) { // Hash array value set to false // if there is line between // two adjacent cell in same row // If query is {0 1 1 1} or // {1 1 0 1} we make row[0][1]= false, // that means there is vertical line // after the cell [0][1] if (q[i, 0] == q[i, 2]) { int mn = Math.Min(q[i, 1], q[i, 3]); row[q[i, 0], mn] = false; } // Hash array value set to false if // there is line between // two adjacent cell in same column // If query is {2 3 2 4} or {2 4 2 3} // we make col[2][3]= false, // that means there is horizontal line // below the cell [2][3] else { int mn = Math.Min(q[i, 0], q[i, 2]); col[mn, q[i, 1]] = false; } } // Store count of total regions after // performing K queries. int TotalRegion = 0; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { // If current Cell // is not visited // then increment the TotalRegion // count and traverse // all the cell in that region if (!vis[i, j]) { TotalRegion++; traverse(i, j, N, M, vis, row, col); } } } return TotalRegion; } // Driver Code public static void Main(string[] args) { int[, ] q = { { 2, 1, 2, 2 }, { 1, 2, 2, 2 }, { 1, 3, 2, 3 }, { 1, 4, 2, 4 }, { 2, 3, 3, 3 }, { 3, 3, 3, 4 }, { 3, 3, 4, 3 }, { 3, 3, 3, 2 }, { 3, 1, 3, 2 }, { 4, 1, 4, 2 } }; int N = 5, M = 5; int K = 10; Console.WriteLine(count(N, M, K, q)); }}// This code is contributed by phasing17 |
Javascript
<script> // JavaScript code to implement the approach // Recursive function to traverse the matrix const traverse = (i, j, N, M, vis, row, col) => { if (i <= 0 || i > N || j <= 0 || j > M || vis[i][j]) return; // Mark Current cell visited. vis[i][j] = true; // Traverse adjacent cells in all directions // (up, down, right, left) that // do not include lines between if (row[i][j]) traverse(i, j + 1, N, M, vis, row, col); if (col[i][j]) traverse(i + 1, j, N, M, vis, row, col); if (row[i][j - 1]) traverse(i, j - 1, N, M, vis, row, col); if (col[i - 1][j]) traverse(i - 1, j, N, M, vis, row, col); } // Function to count the total regions const count = (N, M, K, q) => { let row = new Array(N + 1).fill(1).map(() => new Array(M + 1).fill(1)); let col = new Array(N + 1).fill(1).map(() => new Array(M + 1).fill(1)); let vis = new Array(N + 1).fill(0).map(() => new Array(M + 1).fill(0)); for (let i = 0; i < K; i++) { // Hash array value set to false // if there is line between // two adjacent cell in same row // If query is {0 1 1 1} or // {1 1 0 1} we make row[0][1]= false, // that means there is vertical line // after the cell [0][1] if (q[i][0] == q[i][2]) { let mn = Math.min(q[i][1], q[i][3]); row[q[i][0]][mn] = false; } // Hash array value set to false if // there is line between // two adjacent cell in same column // If query is {2 3 2 4} or {2 4 2 3} // we make col[2][3]= false, // that means there is horizontal line // below the cell [2][3] else { let mn = Math.min(q[i][0], q[i][2]); col[mn][q[i][1]] = false; } } // Store count of total regions after // performing K queries. let TotalRegion = 0; for (let i = 1; i <= N; i++) { for (let j = 1; j <= M; j++) { // If current Cell // is not visited // then increment the TotalRegion // count and traverse // all the cell in that region if (!vis[i][j]) { TotalRegion++; traverse(i, j, N, M, vis, row, col); } } } return TotalRegion; } // Driver code let q = []; let N = 5, M = 5; let K = 10; q.push([2, 1, 2, 2]); q.push([1, 2, 2, 2]); q.push([1, 3, 2, 3]); q.push([1, 4, 2, 4]); q.push([2, 3, 3, 3]); q.push([3, 3, 3, 4]); q.push([3, 3, 4, 3]); q.push([3, 3, 3, 2]); q.push([3, 1, 3, 2]); q.push([4, 1, 4, 2]); document.write(count(N, M, K, q));// This code is contributed by rakeshsahni</script> |
Output
2
Time Complexity: O( N*M + Q )
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!
