这道题我戏称为“迷宫题”。回忆一下小时候在公园里,是否遇到过这样一种简陋迷宫,迷宫里不断的转圈,最终你进入了一个圆圈的中心,可能有个小广场,小雕塑,或是小房子在那里等着你。
这道题只不过把圈圈变成了正方形罢了。处于中心位置的数,恰好是 n*n.
不知道上述的描述会不会给你什么启发,而我就是完全依照这个思路去解的,所以效率也许并不高,也说不出这属于那种算法的范畴。以三维矩阵为例,设行为i, 列为j,如果把最外圈转一遍,记录步骤如下表:
i | j | 条件 | 动作 |
---|---|---|---|
0 | 0 | i==0 && j!=n-1 | ++j |
0 | 1 | i==0 && j!=n-1 | ++j |
0 | 2 | i==0 && j!=n-1 | ++j |
1 | 2 | j==n-1 && i!=n-1 | ++i |
2 | 2 | j==n-1 && i!=n-1 | ++i |
2 | 1 | i==n-1 && j!=0 | --j |
2 | 0 | i==n-1 && j!=0 | --j |
1 | 0 | j==0 && i!=0 | --i |
0 | 0 | j==0 && i!=0 | --i |
可以发现,最后我们又回到了原点,却没有像我们想象的那样,停在[1][0]的地方,在迷宫里,这个地方意味着你面对着一堵墙,你不能去撞墙,而是要右转进入下一个圈圈。
程序里,我们就要为墙所在的地方设置标记位。换句话说,我们也可以给不为墙的地方设置标记位,如给二维数组初始化时,将值设为 -1.那么走过的地方自然不可能为 -1,就成了墙。
所以转圈停止的条件为: Matrix[i][j] != -1;
ok,如果将每一步产生的值记录下来(设为value, 每走一步就自加), 那么当 value == nn 的时候就算走到了中心。如果不等于 nn,就要向里面再转一圈。
思路很清楚了,我觉得这个解法很直接,代码也并不繁复,非常好理解。请大家拍砖。