在字符行中查找形状-Java

Question

我在思考如何从字符行中获取形状时遇到了问题，例如给定以下输入：

AAAAAAAA    
ABBBAABA
ABABABBB
ABBBAAAA
AAAABBAA
ABBABBAA
ABBABBAA
ABAABBAA

任务：计算水平或垂直相邻的 'B' 个字母组成的形状有多少。在这个例子中有 4 个这样的形状。如果我删除“A”可能会更容易看到：

 BBB  B 
 B B BBB
 BBB    
    BB  
 BB BB  
 BB BB  
 B  BB

附加任务：每个形状有多少 'B' 个字符？在此示例中：8、4、5、8（没有任何特定顺序）。

我对Java还是个新手，所以我想问一下有没有java函数可以检查彼此靠近的相同事件以计算出现的形状？希望你能给我一些关于如何构建这个算法的指导。（我想过获取 'B' 的每个索引并检查它们是否靠近其他 'B' 但我卡住了）

Answer 1

int indexCount = 0;
ArrayList<Integer> list = new ArrayList<Integer>();

for(int a = 0; a < count; a++) {
    indexCount = array[a].indexOf('B');
    list.add(indexCount);
}

System.out.println(list);

Answer 2

方法indexof(int ch) returns 字符串中出现字符的第一个索引。你应该在得到第一个 B 的索引后切割每个字符串。

或者您可以使用 indexOf(int ch, int fromIndex) 即 returns 指定字符在该字符串中第一次出现的索引，从指定索引处开始搜索。

Answer 3

I am still new to Java, so I want to ask is there is any java function that can check the same occurrence that near to each other in order to count the shape appears?

不，没有内置功能可以让这一切变得非常简单。这就是练习的重点。

以下是您可以用来解决此问题的一些示例方法：

Flood fill:
- 将输入转换为矩阵。它可能是一个 boolean[][]，您在其中设置 true，其中输入是 B。
- 迭代矩阵中的值，跳过 false 个值。
- 当您找到 true 值时，启动洪水填充：
  - 增加形状的数量（您发现了一个新形状）
  - 递归地用 false 替换所有相邻的 true 值，递增 shapeSize 计数
  - 当所有 true 个邻居（以及邻居的邻居，等等）被替换为 false 时，形状被完全探索
  - 从中断处继续迭代，直到找到另一个 true 值
图论：求connected components
- 将输入转换为无向图：
  - 每个字符的索引可以是顶点id
  - 为输入
- 迭代图的顶点
- 如果一个顶点还没有一个组件id，使用深度优先搜索找到所有连接到它的顶点，为所有顶点分配下一个组件id，递增componentSize计数去
- 当没有更多的连接顶点时，形状被完全探索
- 从中断处继续迭代，直到找到另一个没有组件 ID 的顶点
Union find：这类似于查找连通分量

在字符行中查找形状-Java

Find shape within rows of characters-Java

java

arrays

list

shape

count