首页 > 代码库 > 【基础题】蛇形填数

【基础题】蛇形填数

题目描述

在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的值。(n<=100)

输出

输出结果是蛇形方陈。

样例输入

3

样例输出

7 8 1
6 9 2
5 4 3

先说一下我的思路,
我把n=4时的情况列了出来,发现了奇数时,j变化,偶数时,i变化等变化规律,后来我发现需要总结很多变化规律才能算数来,总结出了n=4的,n=5时又不一样了,哎,头疼(小白的思路。。)
大神们的思路:

这是个4连通问题。
针对每个方阵中的格子,与它四连通相邻的格子有4个:左右和上下;
要想访问它们有四个方向:向下y坐标加1,纵坐标加0,记为(0,1),顺时针是向左(-1,0),然后是(0,-1),最后是(1,0);可用一个方向数组存储这四个方向,切换时按顺序选取。
数组开设好,填充为0值;
种子格子为数组右上方元素填入第一个计数1,下面第一方向为(0,1),按照这个方向如果发现新格子在数组坐标内且其值为0,则进行填充,再按照方向继续填充;
如果发现上面条件不满足换第二个方向(-1,0)继续填充;
直到当前格子的四个方向均不满足填充条件时结束。
这样得到的就是所谓蛇形填数的结果,而且与方阵尺寸无关。

②这个方法比较容易理解而且也简单不过只能对这个题:
数组开设好,填充0,遍历先右下,再左,再左上,再右。遍历过的设为1,即能实现蛇形遍历。

核心代码:
while (val<n*n)  
    {  
        while (x+1<n && !a[x+1][y])   a[++x][y]=++val;  
        while (y-1>=0 && !a[x][y-1])  a[x][--y]=++val;  
        while (x-1>=0 && !a[x-1][y])  a[--x][y]=++val;  
        while (y+1<n && !a[x][y+1])   a[x][++y]=++val;  
    }  

完整代码如下:

#include <cstdio>  
#include <cstring>  
#define MAXN 10  
int a[MAXN][MAXN];  
int main()  
{  
    int n, x, y, val=0;  
    scanf("%d",&n);  
    memset(a,0,sizeof(a));// clear array  
    val=a[x=0][y=n-1]=1;// set the first element  
    while (val<n*n)  
    {  
        while (x+1<n && !a[x+1][y])   a[++x][y]=++val;  
        while (y-1>=0 && !a[x][y-1])  a[x][--y]=++val;  
        while (x-1>=0 && !a[x-1][y])  a[--x][y]=++val;  
        while (y+1<n && !a[x][y+1])   a[x][++y]=++val;  
    }  
    for (x=0; x<n; ++x)  
    {  
        for (y=0; y<n; ++y)  
        {  
            printf("%3d",a[x][y]);  
        }  
        printf("\n");  
    }  
    return 0;  
}

 



【基础题】蛇形填数