algorithm - 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 x n)。

除了检查所有可能达到 O(m x n x k!) 的可能性之外，我想不出任何解决方案

Answer 1

在描述中并没有明确说明，但是由于 diagonalAttack 参数是与 rowAttack 和 columnAttack 参数分开指定的，所以似乎是船的“攻击区”形状像星号或星形，而不是实心矩形。在这种情况下，您可以通过将船只放置在彼此偏移 (2, 1)(或 (1, 2))的位置来获得非常紧凑的包装:例如第一个在 (0, 0)，另一个在 (2, 1)，另一个在 (4, 2)，依此类推。 (船只之间的非零垂直和水平偏移分别保证了水平或垂直攻击不会击中任何船只；x 和 y 偏移不同的事实保证了对角线攻击区域也永远不会击中船只。)

一旦到达板的(右或上)边缘，您将需要从(左或下)边缘重新开始。现在事情变得稍微复杂一些，因为你必须小心不要让新船撞到它们下面的现有船或被它们下面的现有船撞到(在撞到右边缘的情况下)。您可以继续使用与之前相同的 x 位置，但将每艘船的 y 位置向上调整到足以避免撞击或被其下方的任何船舶撞击；或者，您可以通过使用与以前相同的 x 位置但将它们偏移 1 来获得更紧密的包装，以消除垂直攻击区域中命中的可能性。

这只是一种试探法:如果未能将所有船只打包到板上，并不一定意味着它们不能打包。但它应该经常快速找到答案，如果你想开发一种使用回溯的精确方法(例如最佳优先搜索)，那么我认为“运行此启发式后成功放置的船只数量”将是一种有用的方法订购部分解决方案。