我想验证战舰领域本规则：

本场重新psented为字节[10] [10] 数组$ P $。 我可以用什么算法来做到这一点？ 我使用的语言是Java，但任何语言是不错的。

The field is represented as byte[10][10] array. What algorithm could I use to accomplish this? The language I use is Java, but any language is good.

推荐答案

一个快速检查的有效性：1×4甲板船，2×3甲板，3×2台，4×1甲板船必须占用恰好1 * 4 + 2 * 3 + 3 * 2 + 4 * 1 = 20个细胞。所以，如果您的域不包含20个细胞，它是无效的（无论是船舶重叠，或没有足够的船舶）

A quick check for validity: 1×4-deck ship, 2×3-deck, 3×2-deck, 4×1-deck ships must occupy exactly 1*4 + 2*3 + 3*2 + 4*1 = 20 cells. So if your field does not contain 20 cells, it is invalid (either ships overlap, or there aren't enough ships)

现在，您需要验证您拥有每种类型船舶的完全正确的数量，以及船舶不碰。您可以通过连接成分分析做到这一点。在简单的两通算法将在这里做的（有一个在链接伪code和例子你）。这会给你在你的领域的每个斑点的大小，位置和形状。

Now, you need to verify that you have exactly the correct number of each type of ship, and that ships do not touch. You can do this through connected component analysis. The simple two-pass algorithm will do here (there's pseudo-code and examples for you in the link). This will give you the size, location and shape of each "blob" in your field.

从那里，你只需要遍历每个斑点，并检查它的垂直或水平线上。这很简单 - 只算一滴的宽度和高度（最大和最小行值之差）（最大和最小列值之差）。其中的一个必须等​​于1。如果没有，那两艘船分别为感动，并现场是无效的。

From there, you just need to iterate over each blob and check that it's either a vertical or horizontal line. That's simple -- just count the blob's width (difference between maximum and minimum column values) and height (difference between maximum and minimum row values). One of these must be equal to 1. If not, then two ships were touching, and the field is invalid.

最后，检查是否有每种船型的正确数目。如果不这样做，那么该字段是无效的。如果你这样做，该领域是有效的，就大功告成了。

Finally, check that you have the correct number of each ship type. If you don't, then the field is invalid. If you do, the field is valid, and you're done.

修改

船舶还可以触摸端至端，但是这样会降低船舶的总体数量（增加于某种类型的数），因而不能最后一次测试

Ships can also touch end-to-end, but this will reduce the overall number of ships (increase the number of ships of a certain type) and thus fail the last test.

编辑2

修正使用正确的船舶规格。

Corrected to use the correct ship specifications.