Java Program to Find the Number of 'X' Total Shapes

In this section, we will solve a problem in which we have to count 'X' shapes in a 2D matrix. The letters in the matrix are either 'X,' or 'O,' where the 'X' represent the part of the form and the 'O' represent space.

The aim is to count the number of distinct linked "X" shapes-a shape is defined as a group of adjacent "X"s-that are present. Neighbours that are adjacent are those that are vertical and horizontal, but not diagonal.

Problem Statement

Given a 2D matrix where each cell is either 'X' or 'O', the objective is to determine how many distinct groups of connected 'X's (shapes) are present.

For example, in the matrix:

There are three distinct 'X' shapes:

1. The first two 'X's in the first row form one shape.
2. The last two 'X's in the second and third rows form the second shape.
3. The last two 'X's in the fourth row form the third shape.

Approach

In order to resolve this problem, one can apply DFS or BFS method for the matrix and count the number of linked 'X's Only. Any unexplored 'X' will be considered as the starting point for a new shape; the 'X's will be drawn in DFS or BFS; counter of shapes will be incremented.

1. Initialize a visited matrix: We maintain a boolean 2D array to keep track of the cells that have already been visited.
2. Iterate over each cell: For each cell, if it contains 'X' and has not been visited, initiate a DFS or BFS from that cell.
3. DFS/BFS to find connected 'X': Once we find an unvisited 'X', we perform DFS/BFS to mark all adjacent 'X' cells as visited.
4. Count the shape: Every time a DFS/BFS is initiated, it corresponds to one new shape.

DFS Algorithm

1. Start with any unvisited 'X': Traverse the matrix.
2. Mark all connected 'X's: Once you find an unvisited 'X', mark it and continue recursively marking all adjacent 'X's.
3. Increment the count: Once all connected 'X's are marked, increment the shape count.

File Name: XShapeCounter.java

Output:

 Number of 'X' shapes: 3 

Explanation

With 'X' cells denoting a portion of a form and 'O' cells denoting empty space in a 2D character grid, the XShapeCounter class counts different 'X' shapes. The countXShapes() method iterates over the grid, tracking processed cells using a visited matrix.

The dfs() method initiates a Depth-First Search (DFS) to search all related 'X' cells in four directions (up, down, left, and right) and mark them as visited when an unvisited 'X' is located. The number of shapes is increased in proportion to the number of DFS calls, which each represent a single form.

Only legitimate, unexplored 'X' cells are examined thanks to the isValid() helper function, which also verifies boundary conditions. The primary method outputs the overall count of different 'X' forms and tests the software on a sample grid.

Conclusion

In conclusion, the Depth-First Search (DFS) method used by the XShapeCounter application effectively counts the number of unique "X" forms in a 2D grid. The software investigates all linked 'X's in four directions (up, down, left, and right), iterating around the grid and marking visited 'X' cells such that each form is tallied only once.

The problem of counting related components in a matrix may be solved in an understandable and efficient manner using this method. The visited matrix guarantees that no cell is handled more than once, improving efficiency, and the algorithm is designed to handle common edge circumstances like empty grids.

This method may be expanded to address related issues with linked elements in matrices or grids.