二维数组中的图形识别
我想识别二维数组（随机播种 0 和 1）中的二维图形（例如俄罗斯方块图形，其中 1 表示填充块，0 表示空平面）。有没有通用的方法？第一个想法是迭代源数组，假设 A[i,j] 是预期图形的原点，并将导出的图形与参考图形进行比较。
对于 100x100 数组和 10x10 数字，这将需要 (100-10)*(100-10)=8100 次操作，这意味着通常 O=n^2 因为可能有很多数字，我对吗？当然可以应用缓存，并且我们可以尝试仅迭代“脏”部分......
但是我认为应该存在更好的解决方案。有人可以指出吗？
I want to recognize 2d figures (for example tetris figures where 1 means filled block and 0 means empty plane) in 2d array (seeded randomly with 0 and 1). Are there any general approaches? First idea is to iterate over source array assuming that A[i,j] is origin point of expected figure and to compare derived figure with the reference one.
For 100x100 array and 10x10 figures this will take (100-10)*(100-10)=8100 operations, and this means O=n^2 in general because there can be many figures am I correct? Of course caching can be applied, and we can try to iterate only over "dirty" sections...
However I suppose better solutions should exist. Can someone point them out?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我采取的一般方法也是 O(n^2)，但似乎在数字（多骨牌）数量上比在块数量上更多。
迭代每个块，如果它已设置（即：其值为 1），则查看其 4 个连接的相邻网格单元。从此（以及任何其他连接的相邻单元格），您应该能够确定它是什么形状，并且可以将这些单元格标记为观察到的，以便在迭代它们时可以跳过它们。这样，您将依次查看每个单元格，但大多数代码仅在您主动在单元格中查找 tromino 时才会执行。
我认为是否提前知道网格中的数字数量非常重要。
The general approach I would take would be O(n^2) as well, but would seem to scale more on the number of figures (polyominoes) than in the number of blocks.
Iterate over each block, if it is set (ie: its value is 1), look at its 4 connecting neighbor grid cells. From this (and any other connecting neighbor cells), you should be able to determine what shape it is, and you can mark those cells as observed, so you can skip them when you iterate to them. This way you would look at each cell in turn, but most of the code only executes when you're actively looking for a tromino in a cell.
I suppose it matters greatly whether the number of figures in the grid is known ahead of time or not.