<蛇形填数>--算法竞赛 入门经典（第2版）- 3.1 数组 程序3-3 蛇形填数

 蛇形填数： 在n×n方阵里填入1,2，....,n×n，要求填成蛇形。例如，n = 4 时方阵为：

　　　    10  11  12  1

　　　  　9  16  13  2

　　　 　 8  15  14  3

　　　 　 7   6    5   4

　　　　上面的方阵中，多余的空格只是为了便于观察规律，不必严格输出。n <= 8 。

　　　　类比上面这种数学中的矩阵，我们可以考虑使用一个二维数组来储存。

　　　解题思路：从右上角开始往下填数，当到底的时候转向左填值，当到左边的边的时候转向上填数，当到最上面的时候转向右填值...依次类推。第一轮转圈的判断条件很简单，就是当横坐标小于行数、纵坐标小于列数的时候。但是这样循环下去当到第二轮循环的时候就会把第一轮的数值覆盖，即一直在最外面的一圈循环下去（当把数值填够之后停止）。我们可以这样解决这个问题：起始把数组置成0，然后在判断转向的时候加上&&非下一个位置上的值即可。

　　　　以下是具体解题的代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define maxn 4

 using namespace std;

 int a[maxn][maxn];

 int main() {

     int i, j;

     /*

     for(i = 0; i < maxn; i++) {

         for(j = 0; j <  maxn; j++)

             a[i][j] = 0;

     }*/

     memset (a,,sizeof(a));//这是cstring中的函数，当然也可以用上面的方法赋值

     a[][maxn-] = ;

     j = maxn-;

     i = ;

     int count = ;///从1开始填数

     /*---------思考下面为什么是错误的???

     while(count < maxn*maxn)

     {

         while(i+1 < maxn && !a[++i][j]) a[i][j] = ++count;

         while(j-1 >= 0 && !a[i][--j]) a[i][j] = ++count;

         while(i-1 >= 0 && !a[--i][j]) a[i][j] = ++count;

         while(j+1 < maxn && !a[i][++j]) a[i][j] = ++count;

     }*/

     while(count < maxn*maxn)//①

     {

         while(i+ < maxn && !a[i+][j]) a[++i][j] = ++count;//②

         while(j- >=  && !a[i][j-]) a[i][--j] = ++count;

         while(i- >=  && !a[i-][j]) a[--i][j] = ++count;

         while(j+ < maxn && !a[i][j+]) a[i][++j] = ++count;

     }

     for(i = ; i < maxn; i++)//输出

     {

         for(j = ; j < maxn; j++)

             printf("%3d",a[i][j]);

         cout << endl;

     }

     return ;

 }

　　 　有兴趣的码友可以考虑一下：

　　　　　1、①处为什么不是 count <= maxn*maxn ;

　　　　　2、②处为什么不是 count++ ;

　　　　　3、②处可不可以改成 while(i+1 < maxn && !a[++i][j]) a[i+1][j] = ++count ;

　　欢迎码友评论，谢谢支持。