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

在本节中，我们将解决一个问题，即计算二维矩阵中的“X”形状的数量。矩阵中的字母可以是“X”或“O”，其中“X”代表形状的一部分，“O”代表空格。

目标是计算独立连接的“X”形状的数量——一个形状定义为一组相邻的“X”——存在的数量。相邻的邻居是垂直和水平的，而不是对角的。

问题陈述

给定一个二维矩阵，其中每个单元格是“X”或“O”，目标是确定有多少个独立的连接的“X”组（形状）。

例如，在矩阵中

有三个独立的“X”形状。

1. 第一行的前两个“X”构成一个形状。
2. 第二行和第三行的最后两个“X”构成第二个形状。
3. 第四行的最后两个“X”构成第三个形状。

方法

为了解决这个问题，可以应用深度优先搜索 (DFS) 或广度优先搜索 (BFS) 方法遍历矩阵并计算连接的“X”的数量。任何未访问过的“X”都将被视为新形状的起点；“X”将在 DFS 或 BFS 中进行遍历；形状计数器将递增。

1. 初始化一个已访问矩阵：我们维护一个布尔二维数组来跟踪已访问过的单元格。
2. 遍历每个单元格：对于每个单元格，如果它包含“X”且尚未被访问，则从该单元格开始 DFS 或 BFS。
3. DFS/BFS 查找连接的“X”：一旦我们找到一个未访问过的“X”，我们就执行 DFS/BFS 来将所有相邻的“X”单元格标记为已访问。
4. 计算形状：每次启动 DFS 或 BFS 时，都对应一个新形状。

DFS 算法

1. 从任何未访问过的“X”开始：遍历矩阵。
2. 标记所有连接的“X”：一旦找到一个未访问过的“X”，就标记它，并递归地继续标记所有相邻的“X”。
3. 递增计数：标记完所有连接的“X”后，递增形状计数。

文件名：XShapeCounter.java

输出

 
Number of 'X' shapes: 3   

解释

XShapeCounter 类在二维字符网格中，用“X”单元格表示形状的一部分，用“O”单元格表示空格，来计算不同的“X”形状。countXShapes() 方法遍历网格，使用已访问矩阵跟踪已处理的单元格。

dfs() 方法启动深度优先搜索 (DFS)，用于搜索四个方向（上、下、左、右）的所有相关“X”单元格，并在找到未访问的“X”时将其标记为已访问。形状的数量会随着 DFS 调用次数的增加而增加，每次调用代表一个形状。

isValid() 辅助函数仅检查合法的、未被探索的“X”单元格，并验证边界条件。主方法输出不同“X”形状的总数，并在示例网格上测试程序。

结论

总之，XShapeCounter 应用程序使用的深度优先搜索 (DFS) 方法有效地计算了二维网格中独立“X”形状的数量。该程序在四个方向（上、下、左、右）上探索所有连接的“X”，遍历网格并标记已访问的“X”单元格，从而确保每个形状只被计算一次。

使用此方法可以以可理解且高效的方式解决矩阵中连接组件的计数问题。已访问矩阵确保每个单元格只被处理一次，从而提高了效率，并且该算法设计用于处理空网格等常见边缘情况。

此方法可以扩展以解决矩阵或网格中相关元素的相关问题。