c++ - 有没有办法递归遍历矩阵的所有可能子矩阵，同时防止访问某些子矩阵？

Question

我的任务是找到矩阵内的所有子矩阵，使得每个计数的子矩阵都满足特定条件，并且也不属于另一个有效子矩阵的一部分。
我的第一个想法是编写一个递归过程，以便我们可以简单地 return每当我们发现它有效时从当前子矩阵(以防止该子矩阵的任何子矩阵被测试)。这是我尝试执行此操作的代码:

void find(int xmin, int xmax, int ymin, int ymax){
    if(xmin > xmax || ymin > ymax){return;}
    else if(works(xmin, xmax, ymin, ymax)){++ANS; return;}

    find(xmin + 1, xmax, ymin, ymax);
    find(xmin, xmax - 1, ymin, ymax);
    find(xmin, xmax, ymin + 1, ymax);
    find(xmin, xmax, ymin, ymax - 1);
}

我当前方法的问题似乎在于它允许多次访问子矩阵，这意味着 return语句是无效的，实际上并没有阻止工作子矩阵的子矩阵被计数，因为它们是从其他矩阵访问的。不过，我认为我编写递归程序的想法是正确的。有人可以指出我正确的方向吗？

Answer 1

显然，您需要一种方法来检查子矩阵是否在之前评估过或包含在更大的解决方案中。此外，您需要考虑到在找到解决方案后，稍后可能会找到一个更大的解决方案，它涵盖了当前找到的解决方案。
一种方法是利用名为 R*-tree 的结构。 ，它允许有效地查询空间(或几何)数据。为此，您可以使用 R-tree implementation from boost .通过使用框(矩形)类型来表示子矩阵，然后您可以将 R 树与查询一起使用 boost::geometry::index::contains (找到以前找到的解决方案，其中包括考虑的子矩阵)和 boost::geometry::index::within (查找包含在新发现的解决方案中的先前发现的解决方案)。
这是 C++11 中的一个工作示例，它基于您的想法:

#include <vector>
#include <numeric>
#include <iostream>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/geometries/register/box.hpp>
#include <boost/geometry/index/rtree.hpp>

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

struct Element
{
    int x, y;
};

struct Box
{
    Element lt, rb;
};

BOOST_GEOMETRY_REGISTER_POINT_2D(Element, long, cs::cartesian, x, y)
BOOST_GEOMETRY_REGISTER_BOX(Box, Element, lt, rb)

template<class M>
bool works(M&& matrix, Box box) {
    // Dummy function to check if sum of a submatrix is divisible by 7
    long s = 0;
    for (int y=box.lt.y; y<box.rb.y; y++)
        for (int x=box.lt.x; x<box.rb.x; x++)
            s += matrix[y][x];
    return s % 7 == 0;
}

template <class T, class M>
void find(T& tree, M&& matrix, Box box, T& result) {
    if (box.lt.x >= box.rb.x || box.lt.y >= box.rb.y) return;
    for (auto it = tree.qbegin(bgi::contains(box)); it != tree.qend(); ++it) return;
    if (works(matrix, box)) {
        // Found a new solution

        // Remove any working submatrices which are within the new solution
        std::vector<Box> temp;
        for (auto it = result.qbegin(bgi::within(box)); it != result.qend(); ++it)
            temp.push_back(*it); 
        result.remove(std::begin(temp), std::end(temp));

        // Remember the new solution
        result.insert(box);
        tree.insert(box);
        return;
    }

    // Recursion
    find(tree, matrix, Box{{box.lt.x+1,box.lt.y},{box.rb.x,box.rb.y}}, result);
    find(tree, matrix, Box{{box.lt.x,box.lt.y+1},{box.rb.x,box.rb.y}}, result);
    find(tree, matrix, Box{{box.lt.x,box.lt.y},{box.rb.x-1,box.rb.y}}, result);
    find(tree, matrix, Box{{box.lt.x,box.lt.y},{box.rb.x,box.rb.y-1}}, result);

    tree.insert(box);
}

template <class T>
void show(const T& vec) {
    for (auto box : vec) {
        std::cout << "Start at (" << box.lt.x << ", " << box.lt.y << "), width="
                  << box.rb.x-box.lt.x << ", height=" << box.rb.y-box.lt.y << "\n";
    }
}

int main()
{
    // Initialize R-tree
    const size_t rtree_max_size = 20000;
    bgi::rtree<Box, bgi::rstar<rtree_max_size> > tree, result;

    // Initialize sample matrix
    const int width = 4;
    const int height = 3;
    int matrix[height][width];
    std::iota((int*)matrix, (int*)matrix + height*width, 1);

    // Calculate result
    find(tree, matrix, Box{{0,0},{width,height}}, result);

    // Output
    std::cout << "Resulting submatrices:\n";
    show(result);

    return 0;
}

在本例中，考虑了以下矩阵:

1  2  3  4
5  6  7  8
9 10 11 12

程序将找到所有元素之和可被 7 整除的子矩阵。输出:

Resulting submatrices:
Start at (0, 2), width=4, height=1
Start at (1, 0), width=3, height=3
Start at (0, 0), width=2, height=2
Start at (0, 1), width=1, height=2

我喜欢你的递归方法的一点是，即使对于 1000×1000 元素的大型矩阵，它也能运行得非常快。