本文主要是介绍“蛇形填数”问题的三种解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
蛇形填数。在n×n方阵里填入1，2，…，n×n，要求填成蛇形。n≤8。
【样例输入】
4
【样例输出】
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4
上面的方阵中，多余的空格只是为了便于观察规律，不必严格输出。
【题目来源】
刘汝佳《算法竞赛入门经典 第2版》程序3-3 蛇形填数
【解析】
输出结果明显是个矩阵，因此可以利用二维数组存储要输出的矩阵数据。
一、原书代码
#include<stdio.h>
#include<string.h>
#define maxn 20
int a[maxn][maxn];
int main(){int n, x, y, tot = 0;scanf("%d", &n);memset(a, 0, sizeof(a));tot = a[x=0][y=n-1] = 1;while(tot < n*n){while(x+1<n && !a[x+1][y]) a[++x][y] = ++tot;while(y-1>=0 && !a[x][y-1]) a[x][--y] = ++tot;while(x-1>=0 && !a[x-1][y]) a[--x][y] = ++tot;while(y+1<n && !a[x][y+1]) a[x][++y] = ++tot;}for(x = 0; x < n; x++){for(y = 0; y < n; y++) printf("%3d", a[x][y]);printf("\n");}return 0;
}这段代码非常简洁，值得好好学习、反复揣摩。
按照原书的陈述，它的简洁性体现在3处：
(1)巧妙赋值：连赋值+数组下标赋值。tot = a[x=0][y=n-1] = 1，只用一条语句实现数组元素、数组下标及累加器tot的赋值，简洁的同时没有牺牲可读性。
(2)移动原则：先判断，再移动。蛇形填数问题本质上是一个绘图问题，它的轨迹由笔的坐标、移动方向、是否移动、移动距离这几个因素决定。先判断，再移动，就能避免无谓的移动导致的后退操作。如果对这一点不甚理解，那么看过后面老金的反面教材就明白了。
(3)逻辑判断的简写：“a[x+1][y]== 0”，简写成“!a[x+1][y]”。
二、老金的反面案例
其实这段代码可学习的地方不止于此，对比下老金的反面案例：
#include<stdio.h>
a[10][10];
int main(){int n, num=1;scanf("%d", &n);int i=0, j=n, iMin=1, iMax=n, jMin=1, jMax=n;while(num<=n*n){for(i++; i<=iMax; i++){a[i][j] = num++;}i--; //每次都要退回去一步jMax--;for(j--; j>=jMin; j--){a[i][j] = num++;}j++;iMax--;for(i--; i>=iMin; i--){a[i][j] = num++;}i++;jMin++;for(j++; j<=jMax; j++){a[i][j] = num++;}j--;iMin++;}for(i=1; i<=n; i++){for(j=1; j<=n; j++){printf("%d ", a[i][j]);if(a[i][j]<10) printf(" ");}printf("\n");}return 0;
}
虽然功能是实现了，但相较原书代码，确实有不小的差距：
(1)代码的简洁性、易读性。老金的代码不但简洁性远远不及原书，而且也比其更难理解。
(2)边界检查。老金虽然当时也想到利用是否已经填过数来判断边界，但只是一个闪念，当时潜意识感觉那样会比较复杂。后来的思路就变成了在填数的过程中动态调整边界。设定上边界、下边界、左边界、右边界分别为：iMin、iMax、jMin、jMax。
可以想象小蛇移动的轨迹都变成了墙，规则是这样的：向下移动一轮，右边界就减1；向上移动一轮，左边界就加1；向左移动一轮，下边界就减1；向右移动一轮，上边界就加1。
可见，这种方式无论从逻辑上还是从代码实现上都比原书复杂。
(3)画笔的移动。老金用的是for循环，其中的i++是在每次循环体结束时执行的，然后再去判断。可见，for循环天生就是先移动、后判断的。这就会导致每次都多移动一次，所以在每次循环结束后就要用i—退回去一次。
由此咱们可以总结一条技巧：如果循环的迭代变量在本循环之外还要进行使用，最好不要用for循环。
(4)i++和++i的选择。原书用的一律是++i，老金的代码一律用的是i++。老金是受了思维惯性的驱使，一直都习惯了用i++。i++是先返后加，++i是先加后返。所以和上第(3)条是一个道理，i++会影响到后面的i的使用，++i则不会。i++相当于明日复明日，++i相当于今日事今日毕。所以，为了避免一个循环的值影响到下一个循环，最好用++i。
三、单循环解法
本题还有一个更巧妙的解法，只用一个while循环就能解决。
方法是引入一个变量direction表示移动方向，分别设定0、1、2、3依次表示四个方向，比如本题分别代表下、左、上、右。然后再建立两个数组di[4]、dj[4]分别表示行、列在每个方向上的变化值。这样用i + di[direction]和j + dj[direction]就可以取得在direction方向上的下一个坐标。在到达边界时通过(direction + 1) % 4就能实现轮流改变方向。
代码如下：
#include<stdio.h>
a[10][10];
int main(){int n, num=1;scanf("%d", &n);int i=0, j=n-1;int direction = 0; // 0: 下, 1: 左, 2: 上, 3: 右int di[4] = {1, 0, -1, 0}; // 下、左、上、右在列上的变化int dj[4] = {0, -1, 0, 1}; // 下、左、上、右在行上的变化while(num<=n*n){//填数a[i][j] = num++;//设定下一个坐标int ni = i + di[direction];int nj = j + dj[direction];/*判定下一个坐标是否到达边界，到达后更改方向，并在新方向上设定下一个坐标*/if ((direction == 0 && (ni == n || a[ni][nj])) || // 到达下边界(direction == 1 && (nj < 0 || a[ni][nj])) || // 到达左边界(direction == 2 && (ni < 0 || a[ni][nj])) || // 到达上边界(direction == 3 && (nj == n || a[ni][nj]))) { // 到达右边界direction = (direction + 1) % 4; // 更改方向ni = i + di[direction];nj = j + dj[direction];}//将新坐标赋给i、ji = ni;j = nj;}//打印矩阵for(i=0; i<n; i++){for(j=0; j<n; j++){printf("%d ", a[i][j]);if(a[i][j]<10) printf(" ");}printf("\n");}return 0;
}这篇关于“蛇形填数”问题的三种解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
