這個問題是一個通用的演算法問題，但我是用 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我上面定義的a ，并且鑒于這0意味著一個“空”插槽，我希望能夠生成patternas a 的所有可能出現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
模式不一定是正方形，但我們假設它不大于?? aMatrix可以包含的大小。
我已經想到了解決這個問題的一些方法，并最終采用了我認為最明顯的方法來解決這個問題，但是我很難弄清楚整個事情的邏輯。
到目前為止，我所擁有的是：
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，因為它標記了一個空槽。
uj5u.com熱心網友回復：
不知何故，你已經走上了正確的軌道。
從邏輯上講，必須做什么是很清楚的。
我們取子模式的左上邊緣。然后我們計算目標矩陣中產生的左上邊緣。
生成的矩陣中的列偏移量，我們將模式復制到的位置，將從 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";
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/387589.html
上一篇：這段代碼運行良好，但運行時間更長。如何在更短的時間內執行？
下一篇：在嵌套函式中傳遞資料