匹配魔方蛇形状的算法

huangapple go评论67阅读模式
英文:

Algorithm to match Rubik snake shape

问题

我正在尝试实现一个魔方蛇的模拟,如果我有一个由字符串000000020000200000020000形成的模型,其中每个字符表示相对块的旋转角度,如果一个块旋转,它会影响其旁边的所有块。

如果0 = 无旋转
1 = 90度
2 = 180度
3 = 270度

如何检查是否通过不同的步骤形成相同的形状200002000000020000200000

我是用Java实现的。

英文:

I am trying to implement a Rubik snake simulation, if I have a model that is formed from the string 000000020000200000020000 24 block which each character means rotation angle for the opposite block, if a block rotated it rotates all blocks next to it.

if 0 = no rotation
1 = 90
2 = 180
3 = 270

how to check if the same shape is formed by different steps 200002000000020000200000

I implement in Java.

匹配魔方蛇形状的算法

答案1

得分: 1

将snake1和snake2称为你的两条蛇。

想象一下,snake1和snake2形成相同的形状。考虑到snake1的第一个块。为了使这两个形状重合,这个块应该与snake2的一个块对齐。snake1的第一个块与snake2的哪个块对齐?

这个问题提供了一个算法的开始。如果snake1的第一个块是蓝色的,那么依次遍历所有蓝色的snake2块,并假设snake1的第一个块与snake2的这个块对齐。snake1的第一个块相对于snake2的这个块可能有两种方向;你需要遍历这两种可能的方向。

一旦你选择了snake2的一个块和一个方向,将(0,0,0)称为snake1的第一个块在空间中的位置,并遍历snake1的所有块,并通过写入代表3D空间中所有可能位置的数组中的blueblack来存储它们的位置。数组中所有不包含块的单元格都标记为empty

在第二个数组中为snake2的块执行相同的操作。

只有当这两个数组表示相同的形状时,这两条蛇才代表相同的形状。

附注:由于这些块是棱柱而不是立方体,如果数组中的一个单元格表示一个立方体,那么在描述单元格包含的内容时,需要比简单的blue/black/empty更加明确。因此,你需要要么:

  • 找到一个更巧妙的表示空间的方式,而不是简单的3D数组;或者
  • 找到关于单元格可能包含的内容的良好描述(类似于“半黑半蓝的方向”)。
英文:

Call snake1 and snake2 your two snakes.

Imagine that snake1 and snake2 form the same shape. Think about the first block of snake1. This block should align with one of the blocks from snake2 in order for the two shapes to coincide. With which block of snake2 does the first block of snake1 align?

This question gives the beginning of an algorithm. If the first block of snake1 is blue, then loop through all the blue blocks of snake2 one after the other, and assume the first block of snake1 aligns with this block of snake2. There are two orientations the first block of snake1 might be in compared to this block of snake2; you'll have to loop through these two possible orientations.

Once you've chosen a block of snake2 and an orientation, call (0,0,0) the position of the first block of snake1 in space, and loop through all the blocks of snake1, and store their position by writing blue or black in an array representing all the possible positions in 3d space. All cells of the array which do not contain a block are marked empty.

Do the same in a second array for the blocks of snake2.

The two snakes represent the same shape if and only if the two arrays represent the same shape.

PS: Since the blocks are prisms and not cubes, if a cell in the array represent a cube, then you need to be a bit more explicit than just blue/black/empty in the description of what a cell contains. So you need to either:

  • find a cleverer way to represent space than a simple 3d array; or
  • find good descriptions of the possible contents of a cell (something like "half-black half-blue in what orientation").

huangapple
  • 本文由 发表于 2020年8月10日 22:34:23
  • 转载请务必保留本文链接:https://go.coder-hub.com/63342299.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定