在更大的矩阵中查找所有可能出现的矩阵

Question

这道题是一道一般性的算法题，但我是用C++写的，因为它是我遇到这道题的语言。假设我有以下功能：

using Matrix = std::array<std::array<uint8_t, 3>, 3>;
void findOccurrences(std::vector<Matrix>& output, const std::vector<std::vector<uint8_t>>& pattern);

假设 pattern 是从 0 到 255 的特定数字模式，可以适合我上面定义的 Matrix，并且假设 0 表示“空“插槽，我希望能够将 pattern 的所有可能出现作为 Matrix.

例如，给定以下模式：

{
  { 1, 2 },
  { 3, 4 }
}

我想接收以下矩阵向量：

1 | 2 | 0
3 | 4 | 0
0 | 0 | 0

0 | 1 | 2
0 | 3 | 4
0 | 0 | 0

0 | 0 | 0
1 | 2 | 0
3 | 4 | 0

0 | 0 | 0
0 | 1 | 2
0 | 3 | 4

图案不一定是正方形，但我们假设它不大于 Matrix 可以包含的尺寸。

我已经想到了一些解决这个问题的方法，最后我认为这是最明显的方法，但我很难弄清楚整个事情的逻辑。

到目前为止我拥有的是：

void findOccurrences(std::vector<Matrix>& output, const std::vector<std::vector<uint8_t>>& pattern)
{
    Pattern curPattern = {0}; //temporary pattern, to store each time the current we work on
    const size_t lineOpts = 3 - pattern.size() + 1; //amount of possible line combinations
    for (size_t i = 0; i < lineOpts; i++) //for each possible combination
    {
        for (size_t j = 0; j < pattern.size(); j++) //for each line in pattern
        {
            const size_t lineInd = j + i; //index of line in curPattern
            const auto& line = pattern[j]; //current line in input pattern
            const size_t colOpts = 3 - line.size() + 1; //amount of possible column combinations for this line
            for (size_t k = 0; k < colOpts; k++) //for each possible column combination
            {
                for (size_t l = 0; l < line.size(); l++) //for each column in line
                {
                    const size_t colInd = l + k; //index of column in curPattern
                    //got stuck here
                }
            }
        }
    }
}

我在这里遇到的问题是我想不出一种方法来继续这个算法而不丢失可能性。例如，从我之前给出的示例结果向量中仅获取选项 0 和 2。另外，这种方法似乎效率低下。

这是正确的方法吗？如果是这样，我错过了什么？

编辑：我们还假设 pattern 不包含 0，因为它标记了一个空槽。

Answer 1

不知何故，您已经走在了正确的轨道上。

逻辑上很清楚必须做什么。

我们取子模式的左上边缘。然后我们在目标矩阵中计算得到的左上边缘。

生成的矩阵中的列偏移量（我们将模式复制到的位置）将从 0 开始并递增到矩阵的大小 - 模式的大小 + 1。

与行偏移相同。

因此，在上述情况下，矩阵大小为 3,3，模式大小为，结果矩阵中的目标位置将为 0,0, 0,1, 1,0 1,1。然后我们在这些位置复制完整的图案。

我们需要稍微玩一下索引，但这并不复杂。

我已经创建了一个有据可查的示例代码。如果你会读到这里，那么你会立即明白。请参阅以下许多可能的解决方案之一：

#include <iostream>
#include <vector>
#include <array>
#include <cstdint>

constexpr size_t MatrixSize = 3u;

using MyType = uint8_t;
using MatrixRow = std::array<MyType, MatrixSize>;
using Matrix = std::array<MatrixRow, MatrixSize>;
using Pattern = std::vector<std::vector<MyType>>;
using MatrixPattern = std::vector<Matrix>;

MatrixPattern findOccurence(const Pattern& pattern) {

    // Here we will store the resulting matrixes
    MatrixPattern result{};

    // Sanity check 1. Do we have data in the pattern at all
    if (pattern.empty() or pattern.front().empty()) {

        std::cerr << "\n\n*** Error: At least one dimension of input pattern is empty\n\n";
    }
    // Sanity check 2. Does pattern fit at all into the matrix
    else if ((pattern.size() > MatrixSize) or (pattern.front().size() > MatrixSize)) {

        std::cerr << "\n\n*** Error: At least one dimension of input pattern is empty\n\n";
    }
    else {
        // Now, we know that we will have a solution
        // Check, how many horizontol fits we can theoretically have
        // This will be size of  sizeof Matrix - sizeof pattern + 1.
        const size_t horizontalFits{ MatrixSize - pattern.front().size() + 1 };

        // Same for vertical fits
        const size_t verticalFits{ MatrixSize - pattern.size() + 1 };

        // We now know the horizontal and vertical fits and can resize the
        // Resulting vector accordingly.
        result.resize(horizontalFits * verticalFits);
        size_t indexInResult{ 0 };

        // For all possible positions of the patern in the resulting matrix
        for (size_t startRowInResultingMatrix{ 0u }; startRowInResultingMatrix < verticalFits; ++startRowInResultingMatrix)
            for (size_t startColumnInMatrix{ 0u }; startColumnInMatrix < horizontalFits; ++startColumnInMatrix) {

                // Now we have the upper left edge position of the pattern in the matrix
                // Copy pattern to that position
                for (size_t rowOfPattern{ 0u }; rowOfPattern < pattern.size(); ++rowOfPattern) 
                    for (size_t colOfPattern{ 0u }; colOfPattern < pattern.front().size(); ++colOfPattern) 

                        // Copy. Calculate the correct indices and copy values from sub pattern to matrix
                        result[indexInResult][startRowInResultingMatrix + rowOfPattern][startColumnInMatrix + colOfPattern] = pattern[rowOfPattern][colOfPattern];

                // Next sub matrix
                ++indexInResult;
            }
    }
    return result;
}
//  Driver/Test code
int main() {

    // Pattern to insert
    Pattern pattern{
        {1,2},
        {3,4}
    };

    // Get the result
    MatrixPattern matrixPattern = findOccurence(pattern);
    
    // Show output
    for (const Matrix& matrix : matrixPattern) {
        for (const MatrixRow& matrixRow : matrix) {
            for (const MyType& m : matrixRow)
                std::cout << (int)m << ' ';
            std::cout << '\n';
        }
        std::cout << "\n\n";
    }
}

在更大的矩阵中查找所有可能出现的矩阵

Finding all possible occurrences of a matrix in a larger one

c++

algorithm

matrix