Saturday, November 2, 2024
Google search engine
HomeData Modelling & AIFind the number of ‘X’ total shapes

Find the number of ‘X’ total shapes

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
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.


Output

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:

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!

Last Updated :
21 Feb, 2023
Like Article
Save Article


Previous

<!–

8 Min Read | Java

–>


Next


<!–

8 Min Read | Java

–>

RELATED ARTICLES

Most Popular

Recent Comments