blogger

skytoup's blog

分享经验, 共同进步; RSS: http://blog.skytoup.com/feed

文章44

分类0

评论0

CodeWars kata Conway's Game of Life - Unlimited Edition

题目链接: https://www.codewars.com/kata/52423db9add6f6fc39000354/c

题目大概翻译(99.9%机翻?):

给你一个二维数组 和 经过多少代, 模拟计算Conway's_Game_of_Life的n个时间点

游戏规则:

  • 任何具有少于两个活邻居的活细胞都会死亡,好像是由于人口不足造成的。
  • 任何具有三个以上活邻居的活细胞都会死亡,就像人满为患一样。
  • 任何有两个或三个活邻居的活细胞都可以存活到下一代。
  • 具有正好三个活邻居的任何死单元将变为活单元。

每个单元的邻域是它周围的8个单元(即Moore邻域). 空间在x和y维度上都是无限的,并且所有单元格最初都是死的, 除了指定单元格为活的。返回值应该是围绕所有活细胞裁剪的二维数组。(如果没有活细胞,则返回[[]]。)

出于说明目的,将0和1分别表示为░░和▓▓块(PHP,C:纯黑色和白色正方形)。您可以利用该htmlize功能来获取Universe的文本表示形式,例如:

char *universe = htmlize(cells, rows, columns);
printf(universe);
free(universe);

在C语言中,GoL空间的初始尺寸通过指针和的引用传递到函数中。在扩展/收缩GoL空间时,请通过这两个变量(rowptr, colptr)来跟踪修改后的网格的尺寸。

题目解析
  • 场景大概是有一个二维空间, 上面有一堆活或死的细胞, 每经过一代都根据游戏规则计算细胞的活/死
  • 输入

    • 一个二维数组(0, 1), 代表每个细胞的 活/死 状态
    • 一个int, 代表经过多少代
    • C语言才有: 两个尺寸的指针, 代表输入的二维数组的大小, 也是输出的二维数组的大小
  • 输出一个二维数组(0, 1), 代表每个细胞的 活/死 状态
其它注意的点
  • 单元的邻域是指周围的8个单元格(上、下、左、右、左上、右上、左下、右下)
  • 空间是无限的, 没有边界, 即输入的二维数组大小和输出的二维数组大小不一定相同(已踩坑, 以为在输入的二维数组大小做计算就好了, 谁知道是二维数组是可扩展的...)
  • 输出的空间是围绕着活细胞裁剪的二维数组, 即二维数组最外层四周至少有一个活细胞, 否则空间需要缩小
  • 输入的二维数组的数据需要深拷贝
思路(苦逼的C语言解题...)
  • 一开始的想法

    • 创建并初始化两个二维数组, 一个为现在这代的细胞状态(cur_cells), 另一个是下一代的细胞状态(next_cells)
    • 遍历cur_cells, 根据游戏规则计算每个细胞的状态存到next_cells
    • 最后cur_cellsnext_cells指针互换, 重置next_cells数据为0
  • 一番思考之后?

    • 遍历起来的时候, 重复访问了不少单元格
    • 可以把next_cells改为cal_cells, 作用是单元格周围有多少活细胞
    • (其实不用两个数组也可以, 一个数组足够存储数据, 可分高4低4位存储, 由于太懒了, 没去弄...)
  • 优化之后?

    • 遍历cur_cells, 如果是活细胞, 把对应的cal_cells周边8个单元格数字+1
    • 遍历cal_cells, 根据游戏规则计算每个细胞的状态存到cur_cells
    • 最后重置cal_cells
  • 采坑...?

    • 代码提交上去, 简单测试通过了, 但是随机测试一直无法通过
    • 一番折腾之后, 发现边界是不限定的, 可无限扩张, 或者需要收缩
    • 由于用的是C, 一开始考虑的是realloc+memmov方案, 后来发现随机测试的二维数组大小最大也就100 * 100这样子
    • 最后干脆创建150*150的二维数组用来计算, 初始数据存在数组中央位置(计算偏移位置); 然后每次计算状态之后, 再计算扩展边界; n代过去之后, 再计算收缩的偏移位置, 输出到新的二维数组返回
评论(0)

© 2020  skytoup's blog  · 由 Typecho 强力驱动
  Design by 往记