在careercup 网站上面看到一道amazon的面试题 但是题目看不懂 求大神解释一下

网址如下
http://www.careercup.com/question?id=5380513791475712
请大神解释一下 这道题到底是啥意思
跪谢

看得我脑袋迷糊
0.0

有木有 大神呀

有8个雕像，0,1,2,3,4,5,6,7，每一个雕像指向“North, South, East or West.”中的某一个方向。
按照给的input，就是每一个雕像具体指的某个方向，通过如下规则：
每次只能选取ABCDEFGHZ中的一个，比如你选择A，就只能转动雕像0和1，选择B，只能转动雕像0，1，2.
顺时针转动90度，具体说来就是可行的是E->S, S->W, W->N, N->E.
Move
A: 0,1
B: 0,1,2
C: 1,4,5,6
D: 2,5
E: 3,5
F: 3,7
G: 5,7
H: 6,7
使得全部雕像指向同一方向的最少步数。
Test Case 3:
input: NNSEWSWN
Output: 6
Exp: John uses Move A twice, B once, F twice, G once. This will result in all statues facing W.
首先选择A两次，将0和1由N转到S的位置，
然后选择B一次，将0，1，2转到W的位置。
再选择F两次，将3 E->W，7 N->S
G一次,5 S->W, 7 S->W
由此，全部的雕像都指向W。

Limos 发表于 2014-8-19 16:10
有8个雕像，0,1,2,3,4,5,6,7，每一个雕像指向“North, South, East or West.”中的某一个方向。
按照给的i ...

灰常感谢

这题就是直接的BFS，使用位运算来对状态进行编码，特别的，我对N，E，S，W以编码成对应3位二进制位的四个数0，1，2，3。之所以选择用3位而不是2位是因为在3位的情况下，我们可以很容易的通过下列式子转到新的状态：newState = (state + moves[i]) & MASK。moves[i]会在对应受第i+1号操作（因为是zero-based）影响的statues位置上置1。由我们的编码可知要转到新方向就只是简单的做加法就可以了。唯一需要注意的是位置状态值是3的情况，这时候+1的结果需变回0，所以只要在与上设计好的掩码就可以了。

python代码在： https://gist.github.com/ryancooper/c385cdb4650cecd6ec1c

其实这题还有个更快的方法，就是构造模4的同余方程组，然后通过结合辗转相除法的高斯消元解出来（我们可以预先算出逆矩阵）。如果把逆矩阵hard code进程序，那么基本只要常数时间就能求出任意输入的解。

ryancooper 发表于 2014-8-20 15:45
这题就是直接的BFS，使用位运算来对状态进行编码，特别的，我对N，E，S，W以编码成对应3位二进制位的四个数 ...

0.0 我用bfs来做吧 你说的方法太高端