有趣的算法（九） ——蛇形数组

有趣的算法（九）——蛇形数组

（原创内容，转载请注明来源，谢谢）

一、问题阐述

给定一个数字，需要返回的内容如下图所示：

输入5，得到结果：

输入10，得到结果：

输入一个数字i，输出结果的矩阵是i行i列的。矩阵从右上角开始，从1开始往下，每增加1行加1。到第i行后，再往左，每左一列加1。到头后再往上、往右、再往下....，其中已经填上的数字不能覆盖，直接转向。因为其生成的过程类似盘旋的蛇，故称为蛇形数组。

现要求输入任意元素i，返回矩阵内容。

二、问题分析

初看问题，看似很简单，用几个循环就可以解决问题。但是，当真正开始写循环的时候，就容易卡住。

对于此问题，用循环解决，需要考虑边界条件，以及如何进行循环。

1）如何进行循环

根据蛇形数组的生成过程，由左上方开始循环。共需要四类的循环，从左上到下、从下右到左、从左下到上、从上左到右，其中的上下左右都是相对的位置。

2）边界问题

循环何时退出，主要有两点：1是不能超过边界，输入的是i，则元素不能超出i；2是不能覆盖原有的内容，所以可以在对每个元素进行赋值的时候进行判断，如果已经有内容，则直接转向。

当触及边界问题，则按照第一点提到的四种循环，按顺序执行。

3）循环结束条件

上述的四个循环，只能完成一次的矩阵内容填充，故还需要一个总的循环。考虑到输入i，结果数组的元素个数是i*i，故循环结束的条件就是当值大于i*i，则结束循环。

三、实现

PHP实现过程如下：

function snakenumber($level){
   $max = $level * $level;//最大数量
   $count = 1;//初始值为1
   //初始从左上方开始
   $row = 0;
   $column = $level - 1;
   $res[$row][$column] = $count;
   while($max > $count)
    {
       while($level > $row+1 && !isset($res[$row+1][$column]))$res[++$row][$column] = ++$count;//从右往下
       while(0 <= $column-1 && !isset($res[$row][$column-1]))$res[$row][--$column] = ++$count;//从下往左
       while(0 <= $row-1 && !isset($res[$row-1][$column]))$res[--$row][$column] = ++$count;//从左往上
       while($level > $column+1 && !isset($res[$row][$column+1]))$res[$row][++$column] = ++$count;//从上往左
}
}

结果如问题阐述中的图示。其中的核心就是四重的循环，并且以结果不能大于 $level * $level作为边界控制条件。

PHP的实现相对来说简易，如果要用Java等强类型语言来实现的时候，需要先初始化整个二维数组。初始化的时候，给每个元素赋值为0，然后php中判断元素是否赋值的代码段!isset($res[$row+1][$column])，换成相应的$res[$row+1][$column]==0，即可作为判断。其余代码类似，不再赘述。

另外，近期个人事务较多，故文章发布较少，预计元旦开始会逐步恢复正常的内容发布。

——written by linhxx 2017.10.31