转载

ACM 蛇形填数

7 8 1 6 9 2 5 4 3



看到这个题，首先想到的是有没有一种数学公式，可以根据行列坐标直接得出相应的值。但是思考了半天后没有结果。于是打算试一下最原始的方法，从第一个数1一直向下填，
碰到边界和已经填过的位置就改变方向，方向顺序是下、左、上、右，这是一个循环，正好圈成一个正方形，继续循环，一层一层向里圈正方形，直到把所有的数都填完。

原理已经很明白了：
下面是我的代码：

#include <stdio.h> #include <stdlib.h> //#include <windows.h> //这里直接用int替代Point结构体就行 typedef struct _point{  int rn; } Point; //方向循环 enum DIR {  DOWN,LEFT,UP,RIGHT }; int main() {  int n, i, r, c, nr, nc;  DIR curDir = DOWN;  Point* curPoint;  scanf("%d", &n);  Point* points = (Point*)malloc(sizeof(Point) * n * n);  nr = r = 0;  nc = c = n - 1;  for(i = 0; i < n * n; i++)  {   curPoint = &points[r*n + c];   curPoint->rn = i + 1;   //探测下一个点   switch(curDir)   {   case DOWN:    nr = r + 1;    break;   case UP:    nr = r - 1;    break;   case LEFT:    nc = c - 1;    break;   case RIGHT:    nc = c + 1;    break;   default:    break;   }   //碰到边界和已经填过的 就改变方向   if(nr < 0 || nr >= n || nc < 0 || nc >= n || points[nr*n + nc].rn > 0)   {    curDir = (DIR)((int)curDir + 1);    if((int)curDir >= 4)     curDir = (DIR)0;    nr = r;    nc = c;   }   //根据改变的方向确定下一个位置   switch(curDir)   {   case DOWN:    r++;    break;   case UP:    r--;    break;   case LEFT:    c--;    break;   case RIGHT:    c++;    break;   default:    break;   }  }  //输出  for(i = 0; i < n * n; i++)  {   curPoint = &points[i];   printf("%3d ", curPoint->rn);   if((i+1) % n == 0)    printf("/n");  }  free(points);  //system("pause");  return 0; }

查看了下往上的其他代码，大体上都是这种原理，不同的就是代码实现上的差异了（不过还是感觉我的代码比较符合正常人的思维:-D）

贴上其他人的代码：

#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;   }

目前网上最好的解法，相对比较难以理解：

  #include<stdio.h> int main() {  int a,b,c,d,n,sum=1;  int yi[101][101];  scanf("%d",&n);  for(a=0;a<=(n-1)/2;a++)  {   for(b=a;b<=n-a-1;b++)    yi[b][n-a-1]=sum++;   for(b=n-2-a;b>=a;b--)    yi[n-a-1][b]=sum++;   for(b=n-a-2;b>=a;b--)    yi[b][a]=sum++;   for(b=a+1;b<n-a-1;b++)    yi[a][b]=sum++;  }  for(c=0;c<n;c++)  {   for(d=0;d<n;d++)    printf("%d ",yi[c][d]);   printf("/n");  } }