HZNUOJ 1601 方阵填数

HZNUOJ 1601 方阵填数

HZNUOJ 1601 方阵填数（蛇形填法）

题目描述

Description
在一个N x N的方阵中，填入1，2，……N，共N x N（N≤10）个数，并要求构成如下的格式：

例：

N=513 14 15 16  112 23 24 17  211 22 25 18  310 21 20 19  49	8  7  6  5N=616 17 18 19 20  115 30 31 32 21  214 29 36 33 22  313 28 35 34 23  412 27 26 25 24  511 10  9  8  7  6

Input
N

Output
方阵。

同一行的数字用空格隔开。每行末尾不要有多余的空格。

解题思路和注意点

本题的是个相对简单的找规律的题目，主要是灵活运用二维数组的 i 和 j 下标来确定输出的顺序，使其符合样例规律。通过观察可知，填数的规律是从矩阵外围的右上角从1开始，先沿着列，再沿着行，顺时针累加，对应到二维数组中来，具体如下：

1. 先确定填数停止的条件 ，不止一种，这里采用的是累加的数 k = N² 时，即 N x N 矩阵能填下的所有数都填完了为止；
2. 顺时针填数的步骤可以分解为下左上右，从最外层循环直至最内层填完
3. 下：使列坐标，即 j ，固定为N，使 i 从 1 到 N 改变，从而实现对最外层一列的向下修改，此时 i 循环到了 N ；
4. 左：使行坐标，即 i ，固定为N，使 j 从 N-1 到 1 改变，从而实现对最外层一行的向左修改，此时 j 循环到了 1；

同理，上和右的操作是类似的，但是要注意行列坐标固定的值

5. 上：使列坐标，即 j ，固定为1，使 i 从N-1 到 1 改变；
6. 右：使行坐标，即 i ，固定为1，使 j 从 2 到 N-1 改变；
7. 这样就完成了最外圈的循环，第二圈的操作可以从第 2 行和 第 N-1 列开始，同理第三圈就是从第 3 行和 第 N-2 列开始，如此类推，只需要将 i 和 j 的固定值不停的缩小直到把 N² 填出了为止。

PS：为了方便，可以判断下一步是否重复填写来实现转向（撞到之前填过的位置了需要转向操作了，可以初始化二维数组为0，那么不为0的就是已经填过了），这样可以简化判断转向的条件，具体看代码就能理解

AC代码

#include<stdio.h>
const int N = 105;
int a[N][N]={0};int main(){int n;scanf("%d",&n);int y=n;//列坐标的初始固定值 int x=1;//行坐标的初始固定值int k=1;//填数的初始值 a[x][y]=k;//即方阵右上角的数为1开始 while (k<n*n){while(x<n && !a[x+1][y]) a[++x][y]=++k;//向下操作,!a[x+1][y]即PS里提到的判断下一步转向的简化方法 while(y-1>=1 && !a[x][y-1]) a[x][--y]=++k;//向左操作while(x-1>=1 && !a[x-1][y]) a[--x][y]=++k;//向下操作while(y+1<=n && !a[x][y+1]) a[x][++y]=++k;//向右操作}for (int i=1; i<=n; i++){for (int j=1; j<n; j++){printf("%d ",a[i][j]);	} printf("%dn",a[i][n]);}return 0;
}

此题不难，再接再厉！