c - C中的分而治之trominos算法

Question

这是经典divide and conquer问题。我们有一个 2^n * 2^n 板，我们想用 L 形立方体填充它。我们知道棋盘上有一个方 block 我们不能分配一个立方体。此问题也称为 tromino问题(有点)。

问题

我的解决方案适用于 n = 1 和 n = 2。但是当我想进一步概括解决方案 (n > 2) 时，我没有填充所有 block ，其中一些 block 由错误的 L 形立方体部分组成.

程序结构

输入

用户输入n 和缺少的立方体t 在棋盘上的位置。

输出

我们打印充满“trominos”的棋盘。我们为它们中的每一个分配一个值。缺失的 cude 总是得到零值，每个“tromino”包含一个整数值(1、2、3、....)。

解决方案

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

void recursiveSolve(int m, int A[m][m], int A_row, int A_col, int t_row, int t_y, int currBlockNum, int boardSize);

int main(void) {
    int n, m;

    do {
        printf("Give n > 0: ");
        scanf("%d", &n);
    } while (n <= 0);

    m = pow(2, n);

    int A[m][m];

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            A[i][j] = -1;
        }
    }

    int t_row, t_col;

    do {
        printf("Give missing square row coordinate: ");
        scanf("%d", &t_row);
        printf("Give missing square column coordinate: ");
        scanf("%d", &t_col);
    } while (t_row >= m || t_col >= m);

    A[t_row][t_col] = 0;

    recursiveSolve(m, A, 0, 0, t_row, t_col, 1, m);

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
                printf("%2d ", A[i][j]);
        }
        printf("\n");
    }

    return 0;
}

void recursiveSolve(int m, int A[m][m], int A_row, int A_col, int t_row, int t_col, int currBlockNum, int boardSize) {
    if (boardSize == 2) { // fill with L shaped block the area that is blank (no block exist).

        // check first which part of our board if filled up with  a block
        // and then paint the other.
        if (A[A_row][A_col] != -1) { // block exist at the top-left corner
            A[A_row+1][A_col]  = currBlockNum; // paint the bottom-left corner
            A[A_row+1][A_col+1] = currBlockNum; // paint the bottom-right corner
            A[A_row][A_col+1] = currBlockNum; // paint the top-right corner

        } else if (A[A_row][A_col+1] != -1) { // block exist at the top-right corner
            A[A_row][A_col] = currBlockNum; // paint the top-left corner
            A[A_row+1][A_col] = currBlockNum; // paint the bottom-left corner
            A[A_row+1][A_col+1] = currBlockNum; // paint the bottom-right corner

        } else if (A[A_row+1][A_col] != -1) { // block exist at the bottom-left corner
            A[A_row][A_col] = currBlockNum;
            A[A_row][A_col+1] = currBlockNum;
            A[A_row+1][A_col+1] = currBlockNum;

        } else { // block exist at the bottom-right corner
            A[A_row][A_col] = currBlockNum;
            A[A_row][A_col+1] = currBlockNum;
            A[A_row+1][A_col] = currBlockNum;
        }

    } else {
        int A_halfSize = boardSize / 2;

        // the bellow calculations allow us to check which
        // sub-partition of our board includes the missing block,
        // as well as how we should paint the center L shaped block.
        int A_rowCenter = A_row + A_halfSize;
        int A_colCenter = A_col + A_halfSize;


        if (t_row < A_rowCenter) { // missing block in top half
            if (t_col < A_colCenter ) { // missing block is in top left half
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;
            } else { // missing block is in top right half
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter] = currBlockNum;
            }

        } else { // missing block in bottom half
            if (t_col < A_colCenter ) { // missing block is in bottom left half
                A[A_rowCenter][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
            } else { // missing block is in bottom right half
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;
            }
        }

        // solve each sub-partion recursively

        // top-right sub-partion
        recursiveSolve(m, A, A_row, A_colCenter, t_row, t_col, ++currBlockNum, A_halfSize);

        // bottom-right sub-partion
        recursiveSolve(m, A, A_rowCenter, A_colCenter, t_row, t_col, ++currBlockNum, A_halfSize);

        // bottom left sub-partition
        recursiveSolve(m, A, A_rowCenter, A_col, t_row, t_col, ++currBlockNum, A_halfSize);

        // top-left sub-partition
        recursiveSolve(m, A, A_row, A_col, t_row, t_col, ++currBlockNum, A_halfSize);
    }
}

Answer 1

据我所知，策略是将 L 放置在 3 个正方形中恰好占据一个立方体的位置，该立方体不包含已占据的立方体。

换句话说:

• 您将输入方 block 分成 4 个方 block 。
• 其中一个已经有一个被占用的立方体。
• 你放置 L 使得其他 3 个方 block 也恰好有一个被占用的方 block 结束。

因此，您现在有 4 个正方形 - 所有正方形都恰好有一个被占用的立方体。所以现在您可以在这四个方 block 上运行该函数。

现在您可以独立处理 4 个方 block 中的每一个，因为每个方 block 恰好有一个占用的立方体。

那么你的代码有什么问题？

问题是你没有更新被占用的立方体的位置，而只是保持原来的位置。

    // top-right sub-partion
    recursiveSolve(m, A, A_row, A_colCenter, t_row, t_col, ++currBlockNum, A_halfSize);
                                             ^^^^^^^^^^^^
                                             May need update before calling

    // bottom-right sub-partion
    recursiveSolve(m, A, A_rowCenter, A_colCenter, t_row, t_col, ++currBlockNum, A_halfSize);
                                                    ^^^^^^^^^^^^
                                                    May need update before calling

    // bottom left sub-partition
    recursiveSolve(m, A, A_rowCenter, A_col, t_row, t_col, ++currBlockNum, A_halfSize);
                                             ^^^^^^^^^^^^
                                             May need update before calling

    // top-left sub-partition
    recursiveSolve(m, A, A_row, A_col, t_row, t_col, ++currBlockNum, A_halfSize);
                                        ^^^^^^^^^^^^
                                        May need update before calling

对于 4 个调用中的 3 个，您需要更新占用方 block 的位置。

这可以通过多种方式实现。这是一种方法:

void recursiveSolve(int m, int A[m][m], int A_row, int A_col, int t_row, int t_col, int currBlockNum, int boardSize) {
    if (boardSize == 2) {

        // Keep your existing code unchanged here

    } else {
        int A_halfSize = boardSize / 2;

        // the bellow calculations allow us to check which
        // sub-partition of our board includes the missing block,
        // as well as how we should paint the center L shaped block.
        int A_rowCenter = A_row + A_halfSize;
        int A_colCenter = A_col + A_halfSize;

        // Calculate the position of the center cubes
        // as these will be the new occupied cub for
        // 3 of the 4 squares
        int TR_t_row = A_rowCenter - 1;
        int TR_t_col = A_colCenter;

        int BR_t_row = A_rowCenter;
        int BR_t_col = A_colCenter - 1;

        int BL_t_row = A_rowCenter - 1;
        int BL_t_col = A_colCenter;

        int TL_t_row = A_rowCenter - 1;
        int TL_t_col = A_colCenter - 1;



        if (t_row < A_rowCenter) { // missing block in top half
            if (t_col < A_colCenter ) { // missing block is in top left half
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;

                TL_t_row = t_row;  // Roll back to 
                TL_t_col = t_col;  // original occupied cube

            } else { // missing block is in top right half
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter] = currBlockNum;

                TR_t_row = t_row;  // Roll back
                TR_t_col = t_col;

            }

        } else { // missing block in bottom half
            if (t_col < A_colCenter ) { // missing block is in bottom left half
                A[A_rowCenter][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;

                BL_t_row = t_row;  // Roll back
                BL_t_col = t_col;

            } else { // missing block is in bottom right half
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;

                BR_t_row = t_row;  // Roll back
                BR_t_col = t_col;

            }
        }

        // solve each sub-partion recursively

        // Use the 8 new variables for the recursive calls

        // top-right sub-partion
        recursiveSolve(m, A, A_row, A_colCenter, TR_t_row, TR_t_col, ++currBlockNum, A_halfSize);
                                             //  ^^^^^^^^^^^^^^^^^^

        // bottom-right sub-partion
        recursiveSolve(m, A, A_rowCenter, A_colCenter, BR_t_row, BR_t_col, ++currBlockNum, A_halfSize);
                                                   //  ^^^^^^^^^^^^^^^^^^

        // bottom left sub-partition
        recursiveSolve(m, A, A_rowCenter, A_col, BL_t_row, BL_t_col, ++currBlockNum, A_halfSize);
                                             //  ^^^^^^^^^^^^^^^^^^

        // top-left sub-partition
        recursiveSolve(m, A, A_row, A_col, TL_t_row, TL_t_col, ++currBlockNum, A_halfSize);
                                       //  ^^^^^^^^^^^^^^^^^^
    }
}

更新

如果你想避免对多个 L 使用相同的数字，你应该传递一个指向 currBlockNum 的指针。

更改原型(prototype) - 注意 int* currBlockNum:

void recursiveSolve(int m, int A[m][m], int A_row, int A_col, int t_row, int t_y, int* currBlockNum, int boardSize);

主要做:

int currBlockNum = 1;
recursiveSolve(m, A, 0, 0, t_row, t_col, &currBlockNum, m);
                                        ^^^
                                        Notice

在函数中更改所有要赋值的地方——比如

A[A_row+1][A_col]  = *currBlockNum;
                    ^^^
                    Notice

并且每次您递归调用该函数时，首先进行递增 - 例如:

    ++(*currBlockNum);
    recursiveSolve(m, A, A_row, A_colCenter, TR_t_row, TR_t_col, currBlockNum, A_halfSize);