使用递归的 Java 多米诺骨牌平铺 : second if block gets called with already updated values

Question

一个 m x n 的矩形网格，应填充 m*n/2 2x1 多米诺骨牌，可以水平或垂直放置。存在多少种可能的解决方案？

我正在尝试用递归解决这个问题(是的，我知道这可以很容易地用斐波那契计算)。

private static void place(int row, int col, int[][] rectangle) {
  if (canBePlacedHorizontally(row, col, rectangle)) {
    rectangle = deepCopy(rectangle);
    placeHorizontally(row, col, rectangle);
    decideNextMove(row, col, rectangle);
  }
  if (canBePlacedVertically(row, col, rectangle)) {
    rectangle = deepCopy(rectangle);
    placeVertically(row, col, rectangle);
    decideNextMove(row, col, rectangle);
  }
}
private static void decideNextMove(int row, int col, int[][] rectangle) {
  if (rectangleIsFilled(rectangle)) {
    count = count.add(BigInteger.ONE);
  }
  else if(row == rectangle.length -1) {
    place(0, col+1, rectangle);
  }
  else{
    place(row+1, col, rectangle);
  }
}
private static BigInteger calculate(int m, int n) {
  int[][] rectangle = new int[m][n];
  place(0, 0, rectangle);
  return count;
}

deepCopy() 方法只是通过迭代数组并使用 Arrays.copyOf() 来重新创建二维数组。

如果我调用 calculate(2,2) 它首先通过水平添加多米尼奥并将矩形更改为 [[1,1][0,0]] 来正常工作.然后，它转到同一列中的下一行(row=1，col=0)并再次放置水平多米诺骨牌，因此矩形看起来像 [[1,1][1,1]] 。它检测到矩形已填充，并将 count 加 1。 然后，它继续检查是否可以将垂直多米诺骨牌放置在(行 = 1，列 = 0)处，并且数组已准备好，这显然是行不通的。然后它回退并检查是否可以将垂直多米诺骨牌放置在 (row=0, col=0) 与之前的数组 [[1,1][0,0]] 处，这也不起作用。然后就完成了。

令我困惑的是，place 方法中的 canBePlacedVertically if block 是使用"new"参数调用的。在示例中，我希望它首先使用 [[1,1][0,0]] 数组调用该方法，然后使用 [[0,0][0,0 ]] 数组。谁能看到我的问题出在哪里吗？我猜这与数组重复的地方有关，但我不确定......

感谢您的帮助

以下是剩余的方法，如果有人想亲自尝试一下:

  private static boolean rectangleIsFilled(int[][] rectangle) {
    for(int i = 0; i < rectangle.length; i++) {
      if(IntStream.of(rectangle[i]).sum() < rectangle[i].length) {
        return false;
      }
    }
    return true;
  }

  private static boolean canBePlacedHorizontally(int row, int col, int[][] rectangle) {
    // checks if given field is empty and not on the very right and that the field next to it is empty
    return col < rectangle[0].length -1 && rectangle[row][col] == 0 && rectangle[row][col+1] == 0;
  }

  private static boolean canBePlacedVertically(int row, int col, int[][] rectangle) {
    // checks if given field is empty and not on the bottom and that the field below it is empty
    return row < rectangle.length -1 && rectangle[row][col] == 0 && rectangle[row+1][col] == 0;
  }

  private static void placeHorizontally(int row, int col, int[][] rectangle) {
    rectangle[row][col] = 1;
    rectangle[row][col+1] = 1;
  }

  private static void placeVertically(int row, int col, int[][] rectangle) {
    rectangle[row][col] = 1;
    rectangle[row+1][col] = 1;
  }

  // https://stackoverflow.com/a/1564856
  private static int[][] deepCopy(int[][] original) {
    final int[][] result = new int[original.length][];
    for (int i = 0; i < original.length; i++) {
      result[i] = Arrays.copyOf(original[i], original[i].length);
    }
    return result;
  }
}

Answer 1

你的问题是这个方法:

private static void place(int row, int col, int[][] rectangle) {
  if (canBePlacedHorizontally(row, col, rectangle)) {
    rectangle = deepCopy(rectangle);                  // A
    placeHorizontally(row, col, rectangle);           // B
    decideNextMove(row, col, rectangle);
  }
  if (canBePlacedVertically(row, col, rectangle)) {   // C
    rectangle = deepCopy(rectangle);
    placeVertically(row, col, rectangle);
    decideNextMove(row, col, rectangle);
  }
}

当您正确地复制 A 行中的原始矩形时，您会覆盖对原始矩形的引用，从而无法访问原始矩形。

在 B 行中，您修改矩形的副本。

在 C 行中，您使用修改后的副本而不是原始矩形。

要更正您的代码，您不得覆盖对原始矩形的引用。这意味着在 if 语句中，您需要对克隆矩形进行单独引用:

private static void place(int row, int col, int[][] rectangle) {
  if (canBePlacedHorizontally(row, col, rectangle)) {
    int[][] testrectangle = deepCopy(rectangle);      // A
    placeHorizontally(row, col, testrectangle);       // B
    decideNextMove(row, col, testrectangle);
  }
  if (canBePlacedVertically(row, col, rectangle)) {   // C
    int[][] testrectangle = deepCopy(rectangle);
    placeVertically(row, col, testrectangle);
    decideNextMove(row, col, testrectangle);
  }
}