单页网站作用是什么/网络营销论文

蛇形矩阵是由 11 开始的自然数依次排列成的一个矩阵上三角形。

 

 

Input

输入由一个正整数 NN 组成。 (1≤N≤100)(1≤N≤100)

Output

对于每一组数据，输出一个 NN 行的蛇形矩阵。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。

Examples

Input

Copy

3

Output

Copy

1 3 6
2 5
4

Input

Copy

4

Output

Copy

1 3 6 10
2 5 9
4 8
7

题解 :  新思路 :  看规律,其实这非常像 二叉树的层次遍历 ,用队列来解决, 比如 1的孩子是 2 ,3 , 2的孩子4 ,5  .   3 的孩子是6 ... 等等

代码:

 

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std ;
typedef long long LL ;
const int MAX = 150 ;
struct Point{int x ;int y ;};
int vis[MAX][MAX] ;
int a[MAX][MAX] ;
int dx[4] = {1,0,-1,0}; // 下左上右的顺序;
int dy[4] = {0,-1,0,1};
Point s ;
int n ;
int num ;
void bfs()
{s.x = 1 ;s.y = 1 ;queue<Point> Q ;while(!Q.empty()){Q.pop();}Q.push(s) ;vis[s.x][s.y] = 1 ;a[s.x][s.y] = ++num;while(!Q.empty()){Point now = Q.front() ;Q.pop() ;if(num == (n*(n+1))/2 ){break ;}for(int i = 0 ; i<4 ;i++ ){int next_x = now.x + dx[i] ;int next_y = now.y + dy[i] ;if(next_x <1 || next_y<1 || next_x> n || next_y >n )continue ;if(!vis[next_x][next_y] && !a[next_x][next_y] ){vis[next_x][next_y] = 1 ;a[next_x][next_y] = ++num ;Point tmp ;tmp.x = next_x ;tmp.y = next_y ;Q.push(tmp) ;}}}}
int main()
{cin >> n ;if(n<1 || n>100)return 0 ;bfs();for(int i = 1 ; i<=n ; i++ ){for(int j = 1 ; j<=n-i+1 ;j++ ){if(j <=n - i )printf("%d ",a[i][j]) ;elseprintf("%d",a[i][j]);}cout<<endl;}return 0 ;
}