目录
兰顿蚂蚁
从0开始
从残局开始
OJ实战
力扣 面试题 16.22. 兰顿蚂蚁
兰顿蚂蚁
部分内容来自matrix67的博客 Matrix67.com - Home
从0开始
初始时，蚂蚁位于一张空白画布的某个方格里。如果当前蚂蚁在白色方格上，则对当前方格反色，左转 90 度，前进一格；如果当前蚂蚁在黑色方格上，则对当前方格反色，右转 90 度，前进一格。如此反复。
前面16步：
matrix67的博客里有这个程序，在100*100的表格上运行。
到了10000步开始有规律：
到了这里，由于到了程序设置的边界，就停止了，实际上应该是无限进行下去的。
从残局开始
如果在这个时候，不进行格子的初始化，而把蚂蚁放到最开始的地方和方向，会发生什么呢？
第二次、第三次轮回的循环，和第一次都在同一个位置：
蚂蚁的第四次轮回，出现了新的循环：
PS：第1-11670步是第一次轮回，第11671-17629步是第二三四次轮回
第五次轮回，又出现了新的循环：
第六次轮回：
第七次轮回：
第八次、第九次轮回又在第六次轮回的位置：
第十次轮回又在第四次轮回的地方：
第十一次轮回：
第十二次轮回，又在第七次轮回的位置，
而第四次轮回的位置，因为表格大小的限制，已经毁了。
如果表格够大，有可能第十二次轮回就不在这个位置了。
从这里开始，规律已经开始受到表格大小的限制变得不一定准确了。
第十三次轮回，看似被毁掉的循环居然又复原了
第十四次轮回，应该是因为表格大小限制，没有任何循环产生。而且我忘了截图。
第十五次轮回：
第十六次轮回：
附上统计表：
OJ实战
力扣 面试题 16.22. 兰顿蚂蚁
一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。
编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。
网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由 'X' 表示，白色方格由 '_' 表示，蚂蚁所在的位置由 'L', 'U', 'R', 'D' 表示，分别表示蚂蚁 左、上、右、下 的朝向。只需要返回能够包含蚂蚁走过的所有方格的最小矩形。
示例 1:
输入: 0 输出: ["R"]
讯享网
示例 2:
讯享网输入: 2 输出: [ "_X", "LX" ]
示例 3:
输入: 5 输出: [ "_U", "X_", "XX" ]
说明：
K <=
讯享网class Solution { public: vector<string> printKMoves(int K) { m.clear(); r = c = 0; dire = 1;//上右下左0123 rmin = rmax = cmin = cmax = 0; dir = 'R'; while (K--)move(); vector<string>ans; for (int i = rmin; i <= rmax; i++) { string s = ""; for (int j = cmin; j <= cmax; j++) { s += m[i][j] ? 'X' : '_'; } ans.push_back(s); } ans[r- rmin][c- cmin] = dir; return ans; } void move() { if (m[r][c] == 0)dire = (dire + 1) % 4, m[r][c] = 1; else dire = (dire + 3) % 4, m[r][c] = 0; if (dire == 0)r--, rmin = min(rmin, r), dir = 'U'; if (dire == 1)c++, cmax = max(cmax, c), dir = 'R'; if (dire == 2)r++, rmax = max(rmax, r), dir = 'D'; if (dire == 3)c--, cmin = min(cmin, c), dir = 'L'; } map<int, map<int, int>>m; int r, c, dire, rmin, rmax, cmin, cmax; char dir; };
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/73516.html