Given a grid of size N * M consisting of O’s and X’s. The task is to find the number of ‘X’ total shapes.
Note: ‘X’ shape consists of one or more adjacents X’s (diagonals not included).
Examples:
Input: grid = {{X, O, X}, {O, X, O}, {X, X, X}}
Output: 3
Explanation: The grid is:
X O X | X O X | X O X
O X O | O X O | O X O
X X X | X X X | X X X
So, X with bold color are adjacent to each other vertically for horizontally (diagonals not included). So, there are 3 different groups in the given grid.Input: grid = {{X, X}, {X, X}}
Output: 1
Explanation: The grid is:
X X
X X
So, X with bold color are adjacent to each other vertically for horizontally (diagonals not included). So, there is only 1 group in the given grid.
Approach: To solve the problem follow the below idea:
The idea is to apply dfs from every cell having ‘X’ and not visited, mark all its adjacent cells visited if their value is X and increase the answer by one.
Follow the steps to solve this problem:
- Instead of using an extra vector vis of size n*m to keep track of what cell is visited and not, we can simply convert a visited cell having ‘X’ to ‘O’
- Initialize variable ans with 0, it will keep count of connected components having only ‘X‘.
- Make a function dfs(x, y) to mark the whole connected component having only ‘X’ as visited by converting all ‘X’ to ‘O’.
- Run 2 nested loops for iterating over the whole grid
- Check if the current cell is having ‘X‘, then run a dfs from it and convert all cells in its connected component as ‘O’ and
- Increase the variable ans by 1.
- Return variable ans as the answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to run DFS void dfs(vector<vector< char > >& grid, int x, int y) { // Checking whether the cell is within // the matrix bounds if (x < 0 || y < 0 || x >= grid.size() || grid[x].size() <= y) { return ; } // If grid value is X, we update the // grid value as 0 and call the // function recursively for // adjacent nodes. if (grid[x][y] == 'X' ) { grid[x][y] = 'O' ; dfs(grid, x + 1, y); dfs(grid, x, y + 1); dfs(grid, x - 1, y); dfs(grid, x, y - 1); } } // Function to find the number of // 'X' total shapes. int xShape(vector<vector< char > >& grid) { int n = grid.size(); int m = grid[0].size(); int i, j, ans = 0; // Traversing all the cells of the matrix. for (i = 0; i < grid.size(); i++) { for (j = 0; j < grid[i].size(); j++) { // If grid value is X, we increment // the counter and call the // dfs function. if (grid[i][j] == 'X' ) { ans++; dfs(grid, i, j); } } } // Returning the count. return ans; } // Driver Code int main() { vector<vector< char > > grid = { { 'X' , 'O' , 'X' }, { 'O' , 'X' , 'O' }, { 'X' , 'X' , 'X' } }; // Function Call cout << xShape(grid) << endl; return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to run DFS static void dfs( char [][] grid, int x, int y) { // Checking whether the cell is within // the matrix bounds if (x < 0 || y < 0 || x >= grid.length || grid[x].length <= y) { return ; } // If grid value is X, we update the // grid value as 0 and call the // function recursively for // adjacent nodes. if (grid[x][y] == 'X' ) { grid[x][y] = 'O' ; dfs(grid, x + 1 , y); dfs(grid, x, y + 1 ); dfs(grid, x - 1 , y); dfs(grid, x, y - 1 ); } } // Function to find the number of // 'X' total shapes. static int xShape( char [][] grid) { int n = grid.length; int m = grid[ 0 ].length; int i, j, ans = 0 ; // Traversing all the cells of the matrix. for (i = 0 ; i < n; i++) { for (j = 0 ; j < m; j++) { // If grid value is X, we increment // the counter and call the // dfs function. if (grid[i][j] == 'X' ) { ans++; dfs(grid, i, j); } } } // Returning the count. return ans; } public static void main(String[] args) { char [][] grid = { { 'X' , 'O' , 'X' }, { 'O' , 'X' , 'O' }, { 'X' , 'X' , 'X' } }; // Function call System.out.println(xShape(grid)); } } // This code is contributed by lokeshmvs21. |
Python3
# python code # Function to run DFS def dfs(grid, x, y): # Checking whether the cell is within # the matrix bounds if x < 0 or y < 0 or x > = len (grid) or len (grid[x]) < = y: return # If grid value is X, we update the # grid value as 0 and call the # function recursively for # adjacent nodes. if grid[x][y] = = 'X' : grid[x][y] = 'O' dfs(grid, x + 1 , y) dfs(grid, x, y + 1 ) dfs(grid, x - 1 , y) dfs(grid, x, y - 1 ) # Function to find the number of # 'X' total shapes. def xShape(grid): n = len (grid) m = len (grid[ 0 ]) ans = 0 # Traversing all the cells of the matrix. for i in range ( len (grid)): for j in range ( len (grid[i])): # If grid value is X, we increment # the counter and call the # dfs function. if grid[i][j] = = 'X' : ans + = 1 dfs(grid, i, j) # Returning the count. return ans # Driver Code grid = [ [ 'X' , 'O' , 'X' ], [ 'O' , 'X' , 'O' ], [ 'X' , 'X' , 'X' ] ] # Function Call print (xShape(grid)) # This code is contributed by ksam24000 |
C#
// C# code to implement the approach using System; public class GFG { // Function to run DFS static void dfs( char [, ] grid, int x, int y) { // Checking whether the cell is within // the matrix bounds if (x < 0 || y < 0 || x >= grid.GetLength(0) || grid.GetLength(1) <= y) { return ; } // If grid value is X, we update the // grid value as 0 and call the // function recursively for // adjacent nodes. if (grid[x, y] == 'X' ) { grid[x, y] = 'O' ; dfs(grid, x + 1, y); dfs(grid, x, y + 1); dfs(grid, x - 1, y); dfs(grid, x, y - 1); } } // Function to find the number of // 'X' total shapes. static int xShape( char [, ] grid) { int n = grid.GetLength(0); int m = grid.GetLength(1); int i, j, ans = 0; // Traversing all the cells of the matrix. for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { // If grid value is X, we increment // the counter and call the // dfs function. if (grid[i, j] == 'X' ) { ans++; dfs(grid, i, j); } } } // Returning the count. return ans; } static public void Main() { // Code char [, ] grid = { { 'X' , 'O' , 'X' }, { 'O' , 'X' , 'O' }, { 'X' , 'X' , 'X' } }; // Function call Console.WriteLine(xShape(grid)); } } // This code is contributed by lokesh. |
Javascript
// JavaScript code for the above approach // Function to run DFS function dfs(grid, x, y) { // Checking whether the cell is within // the matrix bounds if (x < 0 || y < 0 || x >= grid.length || grid[x].length <= y) { return ; } // If grid value is X, we update the // grid value as 0 and call the // function recursively for // adjacent nodes. if (grid[x][y] == 'X' ) { grid[x][y] = 'O' ; dfs(grid, x + 1, y); dfs(grid, x, y + 1); dfs(grid, x - 1, y); dfs(grid, x, y - 1); } } // Function to find the number of // 'X' total shapes. function xShape(grid) { let n = grid.length; let m = grid[0].length; let i, j, ans = 0; // Traversing all the cells of the matrix. for (i = 0; i < grid.length; i++) { for (j = 0; j < grid[i].length; j++) { // If grid value is X, we increment // the counter and call the // dfs function. if (grid[i][j] == 'X' ) { ans++; dfs(grid, i, j); } } } // Returning the count. return ans; } // Driver Code let grid = [[ 'X' , 'O' , 'X' ], [ 'O' , 'X' , 'O' ], [ 'X' , 'X' , 'X' ]]; // Function Call console.log(xShape(grid)); // This code is contributed by Potta Lokesh. |
3
Time Complexity: O(N * M), as the vector grid is having N * M cells, and each cell is visited at a max of one time.
Auxiliary Space: O(1) If the recursion stack is considered the time complexity is O(N * M)
Related Articles:
- Introduction to Matrix or Grid – Data Structures and Algorithms Tutorials
- Depth First Search or DFS for a Graph
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!