信息学奥赛赛题蛇形填数

蛇形填数

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

　   10 11 12  1

　    9  16 13  2

　    8  15 14  3

　    7    6   5  4

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

【分析】：

　   类比数学中的矩阵，我们可以用一个所谓的二维数组来储存题目中的方阵。只需声明一个int a[MAXN][MAXN]，就可以获得一个大小为MAXN×MAXN的方阵。在声明时，两维的大小不必相同，因此也可以声明int a[30][50]这样的数组，第一维下标范围是0,1,2,…,29，第二维下标范围是0,1,2,…,49。

    让我们从1开始依次填写。设“笔”的坐标为(x,y)，则一开始x=0，y=n-1，即第0行，第n-1列（别忘了行列的范围是0到n-1，没有第n列）。“笔”的移动轨迹是：下，下，下，左，左，左，上，上，上，右，右，下，下，左，上。总之，先是下，到不能填了为止，然后是左，接着是上，最后是右。“不能填”是指再走就出界（例如4→5），或者再走就要走到以前填过的格子（例如12→13）。如果我们把所有格子初始为0，就能很方便地加以判断。

    这段程序充分利用了C++语言简洁的优势。首先，赋值x=0和y=n-1后马上要把它们作为a数组的下标，因此可以合并完成；tot和a[0][n-1]都要赋值1，也可以合并完成。这样，我们用一条语句完成了多件事情，而且并没有牺牲程序的可读性，这段代码的含义显而易见。

    那4条while语句有些难懂，不过十分相似，因此只需介绍其中的第一条：不断向下走，并且填数。我们的原则是：先判断，再移动，而不是走一步以后发现越界了再退回来。这样，我们需要进行“预判”，即是否越界，以及如果继续往下走会不会到达一个已经填过的格子。越界只需判断x+1<n，因为y值并没有修改；下一个格子是(x+1,y)，因此只需a[x+1][y]==0，简写成!a[x+1][y]（其中!是“逻辑非”运算符）。

    细心的孩子也许会发现这里的一个“潜在bug”；如果越界，x+1会等于n，a[x+1][y]将访问非法内存！幸运的是，这样的担心是不必要的。&&是短路运算符。如果x+1<n为假，将不会计算!a[x+1][y]，也就不会越界了。

    至于为什么是++tot而不是tot++，留给孩子们去思考。