c – 六边形网格算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了c – 六边形网格算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2069字，纯文字阅读大概需要3分钟。

内容图文

六边形网格由具有R行和C列的二维阵列表示.第一行总是在六边形网格结构中“前”第二行(见下图).设k为转数.每次转弯时,网格的一个元素是1,当且仅当该元素的前一个转弯为1的邻居数是奇数时.编写在k转后输出网格的C代码.

限制：

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

模拟：image,黄色元素代表’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;
}

解决方法:

对于给定的R和C,您有N = R * C个单元格.

如果你将这些单元格表示为GF(2)中元素的向量,即0s和1s,其中算术执行mod 2(加法是XOR,乘法是AND),那么从一个转向到下一个转换的转换可以用一个N * N矩阵M,所以：

转[i 1] = M *转[i]

您可以对矩阵取幂,以确定单元格在k转的转换方式：

转[i k] =(M ^ k)*转[i]

即使k非常大,如2 ^ 63-1,也可以通过平方乘法求幂快速计算M ^ k：https://en.wikipedia.org/wiki/Exponentiation_by_squaring这只需要O(log(k))矩阵乘法.

然后,您可以将初始状态乘以矩阵以获得输出状态.

从你问题中给出的R,C,k和时间的限制来看,很明显这是你应该提出的解决方案.

内容总结

以上是互联网集市为您收集整理的c – 六边形网格算法全部内容，希望文章能够帮你解决c – 六边形网格算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---