如何验证战舰游戏的场地？

Question

我正在尝试验证 战舰 场地，并使用以下规则：

• 战舰不会接触到边缘或角落；
• 战舰是直的；
• 有1艘4格的战舰、2艘3格的战舰、3艘2格的战舰和4艘1格的战舰。

场地表示为 byte[10][10] 数组。我能用什么算法来实现这个功能？我使用的语言是Java，但任何语言都可以。

- evgeniuz

---

@Tomas 战舰在美国非常有名。"You sunk my battleship!" 但是在我看到的每个版本中，船只相邻或接触都是合法的。Shark，你可以尝试在gamedev.stackexchange.com上发布这个问题。 - Steven

根据原帖所列出的规则，就是我所知道的规则。在我看来，允许船只接触很大程度上会破坏游戏的意义。 - NPE

我认为你需要在你的规则中再添加一些限制，即每种类型的船只数量。一个只有驱逐舰而没有航空母舰的场景在技术上是无效的，但并不违反你列出的任何规则。 - mpenkov

一个鲜为人知的事实是：战舰游戏是作为捷克海军的全面训练演习而发明的。;-) - Ed Staub

@Ed Staub，哈哈哈 :-) “捷克海军”真的是世界上最强大的 :-) 至少我们可以因这个游戏而出名 :-) 你来自哪里？ - Tomas

Answer 1

一个快速的检查：1×4层船，2×3层船，3×2层船，4×1层的船必须恰好占据1*4 + 2*3 + 3*2 + 4*1 = 20个单元格。因此，如果您的船只场地不包含20个单元格，则是无效的（可能是船只重叠或没有足够的船只）。

现在，您需要验证您是否拥有每种类型的船只的正确数量，并且船只不会触碰。您可以通过连通分量分析来实现这一点。这里可以使用简单的两遍算法（链接中提供了伪代码和示例）。这将为您提供每个"blob"在您的场地中的大小、位置和形状。

从那里开始，您只需要迭代每个blob并检查它是否是垂直或水平线条。这很简单——只需计算blob的宽度（最大列值与最小列值之间的差异）和高度（最大行值与最小行值之间的差异）。其中之一必须等于1。如果不是，则两艘船只相互接触，该场地是无效的。

最后，请检查您是否拥有每种船型的正确数量。如果没有，则该场地无效。如果有，则该场地有效，您完成了。

编辑

船只也可以端对端接触，但这将减少总船只数量（增加某种类型的船只数量），因此不符合最后一个测试。

编辑2

修正为使用正确的船只规格。

- mpenkov

---

请注意，第一个快速检查与最终测试是多余的。如果您有一艘5个单位的船，一艘4个单位的船，两艘3个单位的船和一艘2个单位的船，则根据定义，您总共覆盖了17个单位。 - Steven

嗯，这个答案似乎使用的规则与问题不同。我们正在尝试验证哪个版本的战舰游戏？ - Peter Recore

@PeterRecore：糟糕了。我使用了维基百科上的规格来确定船只数量和大小。已经改正。 - mpenkov

Answer 2

伪代码：

initialise the ship map with pairs of (size, amount of ships) values

initialise your map[12][12]:
  for every place at row and column coordinate of 0 or 11 (the border)
    mark it as visited
  for every other place
     mark it as not visited
     fill it with either ship or ocean tile from your input

for each row from 1 to 10
  for each column from 1 to 10
    if that place has not been visited yet
      mark that place as visited
      if that place is a ship tile
        check the places to the "right" (bigger column numbers)
          ... and bottom (bigger "row" numbers)
          until you hit a visited or ocean tile
        the amount of ship tiles checked (including the first) is current ship's length
        decrease the amount of ships of that length in the ship map by one
        mark all ship tiles of the current ship as visited
        mark all tiles surrounding those ship tiles as visited

if the ship map includes any pairs with non-zero (including negative) amount of ships
  the map is invalid
else
  the map is valid

- Martin Sojka

---

我喜欢那种方法，但它无法检测到对角线触碰的情况，是吗？一个解决方案可能是：检查所有围绕找到的船块的瓷砖是否为空（+1） - Thomas

@Thomas：在步骤“标记所有环绕这些船只方块的方块为已访问”中，该算法会“掩盖”任何发现的船只周围的方块，因此任何接触的船只后来都将被切断或者简单消失。这将导致“船只地图”具有非零的“船只数量”值，并且整个地图无效。 - Martin Sojka

Answer 3

简单算法。主要思路：每个“满”场必须被分配给某艘船。

1. 为每种可能的船形状构建一个小矩阵，其中包含其模式，并记录其宽度和高度。每艘船都应以宽度为1的空场边框为边界，以确保不会相邻。
2. 对于每种可能的船形状，遍历战场并检查底层模式-检查船是否存在。
3. 如果模式匹配，即船存在，则只需将所有底部方块标记为属于此船。宽度为1个场的空边缘确保没有其他船/战场边缘接触此船。
4. 重复步骤2和3，以处理所有可能的船型
5. 遍历战场，并检查每个方格是否标记为属于某艘船。如果是，则该场正确。如果不是，则战场不正确。

- Tomas

Answer 4

我不太明白你需要什么： 但我认为战舰游戏中的船只应该具有基本结构：

Ship{
    //x, y: top, left of ship's position
    int: x;
    int: y;
    int: size;//[1,2,3,4]
    boolean: isHorizontal;//It means a ship is vertical or horizontal on the map.
}

如果您将所有船只声明为数组，例如：Ship[SHIP_NUMBER]: arrShip

有一些方法可以检查船只是否重叠

我可以向您展示其中之一：

1. 如果您认为每艘船都是一个矩形，则可以检查是否存在两艘船相交。
2. 如果您认为每艘船都设置在地图上，并且它将保持地图的位置，例如：2层甲板船-水平：shipmap [0] [0] = 1，map [0] [1] = 1。因此，您不能将船只设置在已占用的单元格上。

检查船只是否超出地图范围

1. 您可以检查ship.x < 0 || ship.y < 0 || ship.x > 9 || ship.y > 9

- vietean

---

首先，将字段解析到结构体中实际上是困难的部分。其次，检查重叠船只很容易。航空母舰、战列舰、驱逐舰、潜水艇和巡逻艇必须占据确切的5+4+3+3+2=17个单元格。因此，如果您的字段不包含17个单元格，则无效（船只重叠或者没有足够的船只）。 - mpenkov

Answer 5

由于您最多有10艘船，且数据结构是一个byte数组，为什么不使用值0表示水域，使用值1到10表示船只领域。

然后，您可以迭代字段并检查周围的字段（可以根据迭代方向进行优化，以避免重复检查相同的组合）。

如果遇到值为0，则继续。

如果获得值> 0，则检查周围的字段是否包含除0和该字段值之外的值（检测接触的船只）。

此外，如果周围的字段包含相同的值，但在角落处接触，则说明发现了非法设置。 L形船只也应违反非对角线规则。

最后要检查的是船只是否可能包含孔洞。在这种情况下，只需存储您找到的每艘船的一系列字段，并检查新检查的字段是否紧邻该范围。这也将为您提供船只数量，因为您可以在最后查询每艘船的范围长度。

考虑以下部分板：

    A B C D E F G H I J 
  _____________________
1 | 0 0 2 0 0 0 0 0 0 0
2 | 0 1 0 0 3 3 0 4 0 4
3 | 0 0 0 0 0 3 0 0 0 0

如果你现在检查B2周围的所有字段（其值为1），你会发现值为2的错误。

如果你检查E2，你会发现F3是对角线的，尽管它们的值相同 -> 错误。

如果你检查H2，你会得到范围H2-H2（长度为1），因为H2被空字段包围。如果之后你检查J2，你会发现H和J之间的差值为2（1是可以的），所以你找到了一个重复的船只（或者有一个洞）-> 错误。

基本上，这些规则可以如下表述（适用于非空单元格，即带有船只的单元格）：

- 每个单元格的对角线邻居必须为空（值为0）。 - 每个单元格的直接邻居必须要么是值为0，要么与该单元格的值相同。 - 如果单元格的值已经在列表中，它必须至少有一个与之相同值的直接邻居。

这三条规则应该能够找到任何位置违规的情况，如果你保持每艘船在规则3提到的列表中的范围，你还可以验证船只数量的限制。

- Thomas

Answer 6

我认为使用更好的数据结构来表示棋盘位置将大大简化项目。您可以定义一个Ship类型，其中包含三个字段：船的长度、船的方向和（根据方向）其最上方或最左侧的方块。您将所有想要的船存储在列表中（它将有10个条目）。您通过移动列表来验证您的位置，标记船的所有方块为占用，并将所有相邻的方块标记为禁止。如果在放置船时，您必须将船放置在已占用或禁止的方块中，则知道您有一个无效的位置。另一方面，如果您能够放置所有船而没有冲突，那么您就知道构造正确的棋盘位置。

这样做的额外优点是允许您一次放置一艘船，并立即报告无效配置，这意味着几乎不需要更改与玩家放置船只的用户界面配合工作。

- Pillsy