N皇后变异

Question

给出了NxM矩阵。你有K艘战舰。您还将为每艘战舰提供3个参数- rowAttack、columnAttack和diagonalAttack。每艘船都能攻击一列/列/对角线中的多少个单元格(在每个方向)。你的任务是找出船只是否可以放置在木板上，这样就不会有人互相攻击。

要更清楚地了解攻击，例如，如果该船放置在(5,5)，如果它的列攻击范围为3，那么它可以攻击任何一艘船从(5,2)到(5,8)。

如果不可能这样组合，则返回false。一个示例java类..。

class BattleShip
{
     public final int rowAttack;
     public final int columnAttack;
     public final int diagonalAttack;
}

你需要编码

boolean isPossible(int m, int n, BattleShip battleShips[])

其中m是板中的行数，n是板中的列数，battleShips.length是k，k与m和n都无关。(因此，一个明显的检查是检查k >= m)。

我想不出任何解决办法，只想研究每一个可能上升到O(m！)的可能性。

Answer 1

它在描述中并不明确，但是由于diagonalAttack参数是与rowAttack和columnAttack参数分开指定的，因此似乎船舶的“攻击区域”形状像星号或星号，而不是实心矩形。在这种情况下，你将得到一个非常紧密的包装，将船舶在(2，1) (或(1，2)的偏移:例如，第一个在(0，0)，另一个在(2，1)，另一个在(4，2)，等等。(船舶之间的非零垂直和水平偏移保证船舶不会分别受到水平或垂直攻击；x和y偏移量不同的事实保证，对角线攻击区域也永远不会击中船只。)

一旦你到达板的(右或上)边缘，你将需要重新开始在(左或底部)边缘。事情现在变得稍微复杂一些，因为你必须注意不要让新船撞到或被他们下面的现有船只撞上(如果是撞到右边的话)。您可以继续保持与以前相同的x位置，但将每艘船的y位置向上调整，以避免在其下面的任何船只撞击或撞击；或者，您可以使用与以前相同的x位置，但将其抵消1，从而可以获得更紧密的包装，以消除垂直攻击区域中的命中可能性。

这只是一种启发:如果它不能把所有的船都装到木板上，这并不一定意味着它们就不能装好。但是它通常会很快找到答案，如果你想要开发一种使用回溯的精确方法(例如，最佳优先搜索)，那么我认为“在运行这种启发式之后成功放置的船只数量”将是排序部分解的一种有用方法。

Answer 2

这不是一个有保证的多项式时间解，但实际上它比蛮力要快得多:对于板上的每个方格和每个战舰指数，都有一个0/1的整数变量来表示战舰是否在方格内。然后你可以有线性约束，即每艘战舰都被放置在一个地方，而每艘战舰都被放置在板上，而对于给定的方形和战舰，你不能在该战舰的“射击距离”内，在任何方向上拥有任何战舰。这给了O(mnk)变量中的O(mnk)约束，因此多项式问题描述的复杂性。然后，您可以将您的问题输入到0/1整数编程求解器中，以查看是否有解决方案。对0/1整数规划求解器进行了大量的研究，并在软件中进行了大量的优化，因此在实践中，这可能会比蛮力更快。顺便说一句，我不知道你是怎么得到你引用的关于蛮力的force...the界的，更糟糕的是，O((mn)^k)。