使用动态方法的Tromino平铺[关闭]

Question

为以下任务设计一个算法：给定一个 2n × 2n (n > 1) 的棋盘，其中缺少一个正方形，用只有三种颜色的右三联木平铺它，使得没有任何一对共享边的三联木颜色相同。我打算只实现 3 个数字，即 1,2 和 3，稍后将更改为颜色。

我正在尝试使用动态规划的记忆化方法来解决这个问题，同时将所有板初始化为 0，将缺失的位初始化为 -1，板在平铺之前应该是这样的

0       0       0       0
0       -1      0       0
0       0       0       0
0       0       0       0

平铺后应该是这样的

1        1       3       3
1       -1       2       3
3        2       2       1
3        3       1       1

这里是初始化和解决平铺代码

#include <iostream>

int **board;
int ***memo;

// Function to initialize the board with zeros
void initializeBoard(int n)
{
    int size = 1 << n;
    board = new int *[size];
    memo = new int **[size];
    for (int i = 0; i < size; i++)
    {
        board[i] = new int[size];
        memo[i] = new int *[size];
        for (int j = 0; j < size; j++)
        {
            board[i][j] = 0;
            memo[i][j] = new int[size];
            for (int k = 0; k < size; k++)
            {
                memo[i][j][k] = -1;
            }
        }
    }
}

// Recursive function to solve the tiling problem
int solveTiling(int n, int row, int col, int missingRow, int missingCol, int size)
{
    if (size == 2)
    {
        // Base case: Fill the 2x2 square with cyclic numbers (1, 2, 3)
        int num = 1;
        for (int i = row; i < row + size; i++)
        {
            for (int j = col; j < col + size; j++)
            {
                if (i != missingRow || j != missingCol)
                {
                    board[i][j] = num;
                }
                num = (num % 3) + 1;
            }
        }
        return 0;
    }

    if (memo[n][row][col] != -1)
    {
        return memo[n][row][col];
    }

    int halfSize = size / 2;
    int midRow = row + halfSize;
    int midCol = col + halfSize;
    int result = 0;

    // Check if the missing square is in the top-left quadrant
    if (missingRow < midRow && missingCol < midCol)
    {
        result |= solveTiling(n - 1, row, col, missingRow, missingCol, halfSize);
    }
    // Check if the missing square is in the top-right quadrant
    else if (missingRow < midRow && missingCol >= midCol)
    {
        result |= solveTiling(n - 1, row, midCol, midRow - 1, midCol - 1, halfSize);
    }
    // Check if the missing square is in the bottom-left quadrant
    else if (missingRow >= midRow && missingCol < midCol)
    {
        result |= solveTiling(n - 1, midRow, col, midRow - 1, midCol - 1, halfSize);
    }
    // Check if the missing square is in the bottom-right quadrant
    else if (missingRow >= midRow && missingCol >= midCol)
    {
        result |= solveTiling(n - 1, midRow, midCol, missingRow, missingCol, halfSize);
    }

    if ((row <= missingRow && missingRow < midRow) && (col <= missingCol && missingCol < midCol))
    {
        board[midRow - 1][midCol - 1] = 1;
        board[midRow - 1][midCol] = 1;
        board[midRow][midCol - 1] = 2;
        board[midRow][midCol] = 3;
        result |= 1;
    }
    else
    {
        if (board[midRow - 1][midCol - 1] == 0)
        {
            board[midRow - 1][midCol - 1] = 1;
            result |= 1;
        }
        if (board[midRow - 1][midCol] == 0)
        {
            board[midRow - 1][midCol] = 1;
            result |= 1;
        }
        if (board[midRow][midCol - 1] == 0)
        {
            board[midRow][midCol - 1] = 2;
            result |= 1;
        }
        if (board[midRow][midCol] == 0)
        {
            board[midRow][midCol] = 3;
            result |= 1;
        }
    }

    result |= solveTiling(n - 1, row, midCol, midRow - 1, midCol - 1, halfSize);
    result |= solveTiling(n - 1, midRow, col, midRow, midCol - 1, halfSize);
    result |= solveTiling(n - 1, midRow, midCol, midRow, midCol, halfSize);

    memo[n][row][col] = result;
    return result;
}

这里是打印功能和主要

// Function to print the board
void printBoard(int n)
{
    int size = 1 << n;
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            std::cout << board[i][j] << "\t";
        }
        std::cout << std::endl;
    }
}

// Main function to solve the tiling problem
void tileBoard(int n, int missingRow, int missingCol)
{
    int size = 1 << n;

    solveTiling(n, 0, 0, missingRow, missingCol, size);
    printBoard(n);
}

int main()
{
    int n, missingRow, missingCol;
    std::cout << "Enter the value of n (greater than 1): ";
    std::cin >> n;
    std::cout << "Enter the row and column indices of the missing square (0-based): ";
    std::cin >> missingRow >> missingCol;

    std::cout << "Before tiling:\n";

    initializeBoard(n);
    board[missingRow][missingCol] = -1;

    printBoard(n);

    std::cout << "After tiling:\n";

    tileBoard(n, missingRow, missingCol);

    return 0;
}

这是显示的输出

1       2       1       2
3       1       3       1
1       2       3       2
3       1       3       1

我想知道问题是什么，以便输出更改为预期的输出。 谢谢。