首页 > 代码库 > 【基础题】蛇形填数
【基础题】蛇形填数
题目描述
在n*n方陈里填入1,2,...,n*n,要求填成蛇形。例如n=4时方陈为:
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 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; }
【基础题】蛇形填数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。