logo标签列表

六边形网格上的算法

c++algorithm
3
六边形网格由具有R行和C列的二维数组表示。在六边形网格构建中，第一行始终在第二行“之前”（参见下图）。设k为旋转次数。每次旋转，网格中的一个元素仅在其相邻元素中上一次旋转时为1的数量是奇数时才为1。编写C++代码，输出k次旋转后的网格。
限制条件： 1 <= R <= 10, 1 <= C <= 10, 1 <= k <= 2^(63) - 1
以下是带有输入的示例（第一行为R、C和k，然后是起始网格）：
4 4 3
0 0 0 0
0 0 0 0
0 0 1 0
0 0 0 0

模拟：图片，黄色元素代表“1”，空白代表“0”。

如果我每次模拟并生成一个网格，这个问题很容易解决，但是当k足够大时，速度会变得太慢。有更快的解决方案吗？

编辑：代码（n和m代替R和C）：

#include <cstdio>
#include <cstring>

using namespace std;

int old[11][11];
int _new[11][11];

int n, m;
long long int k;

int main() {

  scanf ("%d %d %lld", &n, &m, &k);

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) scanf ("%d", &old[i][j]);
  }

  printf ("\n");

  while (k) {

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        int count = 0;
        if (i % 2 == 0) {
          if (i) {
            if (j) count += old[i-1][j-1];
            count += old[i-1][j];
          }
          if (j) count += (old[i][j-1]);
          if (j < m-1) count += (old[i][j+1]);
          if (i < n-1) {
            if (j) count += old[i+1][j-1];
            count += old[i+1][j];
          }
        }
        else {
          if (i) {
            if (j < m-1) count += old[i-1][j+1];
            count += old[i-1][j];
          }
          if (j) count += old[i][j-1];
          if (j < m-1) count += old[i][j+1];
          if (i < n-1) {
            if (j < m-1) count += old[i+1][j+1];
            count += old[i+1][j];
          }
        }
        if (count % 2) _new[i][j] = 1;
        else _new[i][j] = 0;
      }
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) old[i][j] = _new[i][j];
    }

    k--;
  }

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

  return 0;
}
展示你的代码！ - DrSvanHay
代码已发布。不知何故忘记了这一点。 - mivan
你一再说“太慢了”。请明确定义什么速度才足够快。这不是捉迷藏，也不是关于编程的问题。 - DrSvanHay
它应该能够在一秒钟内解决它。 - mivan
哎呀，这很有趣。这是某种来自比赛的挑战任务吗？ - DrSvanHay
4个回答
3
给定一个R和C，你有N=R*C个单元格。
如果你将这些单元格表示为在GF(2)中的元素向量，即，在模2下执行算术运算（加法为XOR，乘法为AND）的0和1，则可以通过一个N*N矩阵M表示从一轮到下一轮的转换： turn[i+1] = M*turn[i] 你可以指数化该矩阵以确定单元格在k轮中的转换： turn[i+k] = (M^k)*turn[i] 即使k非常大，例如2^63-1，你也可以使用二分幂快速计算出M^k：https://en.wikipedia.org/wiki/Exponentiation_by_squaring。这只需要O(log(k))次矩阵乘法。
然后，你可以用该矩阵乘以初始状态来获得输出状态。
从问题中给出的R、C、k和时间限制可以看出，这是你应该提出的解决方案。
2
有几种方法可以加速您的算法。
您可以在每次迭代中进行边界检查，计算相邻的单元格。预处理并在开始时计算每个单元格的相邻单元格（Aziuth已经提出了这个方法）。
然后，您就不需要计算所有单元格的相邻单元格。如果上一轮中有奇数个相邻单元格处于打开状态，则每个单元格都是打开的，否则关闭。
您也可以换个角度思考：从干净的板子开始。对于上一个移动的每个活动单元格，切换所有周围单元格的状态。当偶数个相邻单元格导致切换时，该单元格处于打开状态，否则切换会互相抵消。看看您的示例的第一步。这就像玩Lights Out一样。
如果棋盘上只有少量活动单元格，这种方法比计算相邻单元格要快，最坏情况是所有单元格都处于打开状态，此时它与计算相邻单元格一样好，因为您必须触摸每个单元格的相邻单元格。
下一步的逻辑是将棋盘表示为一系列比特，因为比特已经有了自然的切换方式，即异或或xor运算符^。如果你将每个单元格的邻居列表保持为一个位掩码m，那么你可以通过b ^= m来切换棋盘b。
这些是可以对算法进行改进的地方。最大的改进是注意到模式最终会重复出现。(切换类似于康威生命游戏，在那里也有重复的模式。)此外，给定的可能迭代次数2⁶³非常大。
玩板很小。你问题中的例子至少在2¹⁶轮后会重复，因为4×4的棋盘最多只能有2¹⁶种布局。实际上，第127回合达到了原始移动后的环形图案，从那时起，它以126个周期循环。
较大的棋盘可能有高达2¹⁰⁰种布局，因此它们在2⁶³个回合内可能不会重复。一个10×10的棋盘，在中间附近只有一个活动单元格，其周期为2,162,622。正如Aziuth所建议的那样，这确实可能成为数学研究的主题，但我们将用俗世手段来解决它：保持所有先前状态和它们出现的回合的哈希映射，然后检查是否在每个回合中已经出现过该模式。

我们现在有：

  • 一个简单的算法来切换单元格的状态
  • 一个紧凑的位表示棋盘，它允许我们创建先前状态的哈希映射。

这是我的尝试：

#include <iostream>
#include <map>

/*
 *  Bit representation of a playing board, at most 10 x 10
 */
struct Grid {
    unsigned char data[16];

    Grid() : data() {
    }

    void add(size_t i, size_t j) {
        size_t k = 10 * i + j;

        data[k / 8] |= 1u << (k % 8);
    }

    void flip(const Grid &mask) {
        size_t n = 13;

        while (n--) data[n] ^= mask.data[n];
    }

    bool ison(size_t i, size_t j) const {
        size_t k = 10 * i + j;

        return ((data[k / 8] & (1u << (k % 8))) != 0);
    }

    bool operator<(const Grid &other) const {
        size_t n = 13;

        while (n--) {
            if (data[n] > other.data[n]) return true;
            if (data[n] < other.data[n]) return false;
        }

        return false;
    }

    void dump(size_t n, size_t m) const {
        for (size_t i = 0; i < n; i++) {
            for (size_t j = 0; j < m; j++) {
                std::cout << (ison(i, j) ? 1 : 0);
            }
            std::cout << '\n';
        }
        std::cout << '\n';
    }
};

int main()
{
    size_t n, m, k;

    std::cin >> n >> m >> k;

    Grid grid;
    Grid mask[10][10];

    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < m; j++) {
            int x;

            std::cin >> x;
            if (x) grid.add(i, j);
        }
    }

    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < m; j++) {
            Grid &mm = mask[i][j];

            if (i % 2 == 0) {
                if (i) {
                    if (j) mm.add(i - 1, j - 1);
                    mm.add(i - 1, j);
                }
                if (j) mm.add(i, j - 1);
                if (j < m - 1) mm.add(i, j + 1);
                if (i < n - 1) {
                    if (j) mm.add(i + 1, j - 1);
                    mm.add(i + 1, j);
                }
            } else {
                if (i) {
                    if (j < m - 1) mm.add(i - 1, j + 1);
                    mm.add(i - 1, j);
                }
                if (j) mm.add(i, j - 1);
                if (j < m - 1) mm.add(i, j + 1);
                if (i < n - 1) {
                    if (j < m - 1) mm.add(i + 1, j + 1);
                    mm.add(i + 1, j);
                }
            }
        }
    }

    std::map<Grid, size_t> prev;
    std::map<size_t, Grid> pattern;

    for (size_t turn = 0; turn < k; turn++) {    
        Grid next;
        std::map<Grid, size_t>::const_iterator it = prev.find(grid);

        if (1 && it != prev.end()) {
            size_t start = it->second;
            size_t period = turn - start;
            size_t index = (k - turn) % period;

            grid = pattern[start + index];
            break;
        }

        prev[grid] = turn;
        pattern[turn] = grid;

        for (size_t i = 0; i < n; i++) {
            for (size_t j = 0; j < m; j++) {
                if (grid.ison(i, j)) next.flip(mask[i][j]);
            }
        }

        grid = next;        
    }

    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < m; j++) {
            std::cout << (grid.ison(i, j) ? 1 : 0);
        }
        std::cout << '\n';
    }

    return 0;
}

可能还有改进的空间。特别是，我不确定它在大型棋盘上的表现如何。(上面的代码使用了有序映射。我们不需要这种顺序，因此使用无序映射将产生更快的代码。在一个10×10的棋盘上只有一个活跃单元的上面的示例用有序映射花费的时间明显比一秒钟长。)
嗯，在这里无法编译。库的静态断言失败了。 - DrSvanHay
@DrSvanHay：是的，我之前用有序映射写了重复代码，然后认为哈希映射在发布时会更快，这很愚蠢。现在我已经将代码恢复为只使用map而不是unordered_map。它可以工作，但我期望使用哈希映射可以加速。对此我感到抱歉。 - M Oehm
但是“真正”的解决方案不需要任何哈希映射，而且相当优雅。 不过，你必须知道有关伽罗瓦域的知识，但我不知道。 - M Oehm
0

这开始只是一个评论，但我认为作为补充已经被表述过了。

您提出了以下限制：

1 <= R <= 10, 1 <= C <= 10

在这些限制下，我将自行代表网格/矩阵M的R行和C列的常量空间（即O(1)），并通过O(1)而不是O(R*C)时间检查其元素，从而将其从我们的时间复杂度分析中移除。

也就是说，该网格可以简单地声明为bool grid[10][10];。

关键输入是大量回合数k，声明在以下范围内：

1 <= k <= 2^(63) - 1

问题在于，据我所知，您需要执行 k 次操作。这使得算法的时间复杂度为 O(k)。因此，任何提议的解决方案都无法比 O(k) 更好[1]。
为了以意义重大的方式提高速度，必须以某种方式降低这个上限[1]，但看起来这样做可能会改变问题的限制条件。
因此，任何提议的解决方案都无法比 O(k) 更好[1]。 k 可能非常大是主要问题。任何人都只能改进其余部分的实现，但这只能通过一个 常数 因子进行改进；无论如何，您都必须执行 k 次操作。
因此，除非发现一些聪明的事实和/或细节可以降低这个上限，否则就没有其他选择。

[1] 例如，它不像是尝试确定某个数字n是否为质数，您可以检查range(2, n)中的所有数字，以查看它们是否能够被n整除，使其成为一个O(n)的过程，或者注意到一些改进包括在检查n不是偶数后仅查看奇数（常数因子；仍然是O(n)），然后仅检查√n内的奇数，即在range(3, √n, 2)中，这将有意义地将上限降低到O(√n)。

关于O(k)：极其庞大的迭代次数让我怀疑，迟早会像某些生命游戏模式一样陷入循环。游戏场地很小，因此我认为应该使用地图或类似物来检测重复的模式，然后可以计算出最终的模式。 - M Oehm
我甚至尝试使用映射和集合来查找循环，但仍然可能太慢。 - mivan
我不同意必须要在O(k)的概念。如果我们规定每个活动单元格都会使其每个邻居单元格变为活动状态，那么我们只需要计算距离，这显然不需要O(k)的时间。当前问题显然更加复杂，但仍可能存在一种明确的数学公式来计算其中任何一个k下的N个单元格，从而以O(N)的时间进行计算。虽然可能不存在这样的公式，但你并没有证明它。你说“因此，没有任何提出的解决方案可以比O(k)更好”，但你没有提供证明。 - Aziuth
@Aziuth 我认为我已经表明了我的观点。每个回合处理的单元格数量和所需的回合数量不是同一件事。无论每次迭代处理多少个单元格，该问题都需要进行k 回合。由于回合数k也是一个输入，因此它的时间复杂度为O(k)。此外，如果我理解你的意思正确，当你说“如果我们有一个规则…”时，你已经开始猜测了。我们没有你的规则，所以这种推理是没有意义的。 - code_dredd
正如我在我的脚注示例中提到的那样，差异必须是有意义的才能产生影响。 - code_dredd
显示剩余3条评论
0

我不确定你是如何做到的 - 而且你应该总是在这里发布代码 - 但让我们尝试优化一下。

首先，实际上没有什么区别，那和一个二次网格。不同的邻居关系，但我的意思是，那只是一个小的翻译函数。如果你在这方面有问题，我们应该单独处理，也许在CodeReview上。

现在，朴素的解决方案是：

for all fields
    count neighbors
    if odd: add a marker to update to one, else to zero
for all fields
    update all fields by marker of former step

这显然是O(N)的。迭代两次会使实际运行时间增加一倍，但不应该太糟糕。尽量不要每次都分配空间，而是重用现有的结构。

我建议使用以下解决方案：

at the start:
    create a std::vector or std::list "activated" of pointers to all fields that are activated

each iteration:
    create a vector "new_activated"
    for all items in activated
        count neighbors, if odd add to new_activated
    for all items in activated
        set to inactive
    replace activated by new_activated*
    for all items in activated
        set to active

*这可以通过将它们放入智能指针并使用移动语义来高效完成

此代码仅适用于已激活的字段。只要它们保持在某个较小的区域内，这就更加高效。然而，我不知道这何时会改变-如果有激活的字段遍布各地，这可能会 不 高效。在这种情况下，朴素的解决方案可能是最好的。

编辑：现在您已发布了您的代码...您的代码非常程序化。这是C ++，使用类和使用事物的表示。可能您已经正确查找了邻居，但您可能会轻易犯错，因此应将该部分隔离在一个函数或更好的方法中。原始数组很差，而像n或k这样的变量也很差。但是，在我开始撕毁您的代码之前，我更建议您将代码放在CodeReview上，让人们撕掉它直到完美为止。

@mivan，您说k可以接近2^64？那可真是太大了。我猜您的算法单次迭代应该没问题，但迭代次数可能会成为问题。我猜您不关心中间结果，是在寻找如何同时进行多次迭代的数学公式吗？如果是这样，我们可以在这里搜索有关此特定主题的数学论文。考虑到这一点，您可以将其发布在math.stackexchange.com上，作为纯数学问题，与C++部分并行（也就是说，两者都可以做得很好）。 - Aziuth
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接