PTA 7-9 螺旋方阵(20 分)简便解法与复杂解法

时间:2022-02-07 12:26:48

7-9 螺旋方阵(20 分)

所谓“螺旋方阵”,是指对任意给定的N,将1到N×N的数字从左上角第1个格子开始,按顺时针螺旋方向顺序填入N×N的方阵里。本题要求构造这样的螺旋方阵。

输入格式:

输入在一行中给出一个正整数N<10)。

输出格式:

输出N×N的螺旋方阵。每行N个数字,每个数字占3位。

输入样例:

5

输出样例:

  1  2  3  4  5
 16 17 18 19  6
 15 24 25 20  7
 14 23 22 21  8
 13 12 11 10  9
作者: C课程组
单位: 浙江大学
时间限制: 400ms
内存限制: 64MB
代码长度限制: 16KB

最初写这个题解时,比较low,特别复杂,不会优化,这是最初的代码

#include<stdio.h>
#include<math.h>
#define M 100
int main()
{
	int n;
	int ib[M][M];
	int i,j;
	int ia;
	int count=1;
	int temp;
	scanf("%d",&n);
	for(i=0;i<n/2;i++)
	{	
		temp=i;
		ia=0;
		j=i;
		while(ia++<n-2*i)
		{
			ib[i][j]=count++;
			j++;
		}
		ia=0;
		i++;j--;
		while(ia++<n-2*temp-1)
		{
			ib[i][j]=count++;
			i++;
		}
		ia=0;
		j--;i--;
		while(ia++<n-2*temp-1)
		{
			ib[i][j]=count++;
			j--;
		}
		ia=0;
		i--; j++;
		while(ia++<n-2*temp-2)
		{
			ib[i][j]=count++;
	
			i--;
		}
		i=temp;
	}
	if(n%2)
	{
		ib[n/2][n/2]=count;
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			printf("%3d",ib[i][j]);
		}
		printf("\n");
	}
	return 0;
} 

PTA 7-9 螺旋方阵(20 分)简便解法与复杂解法

这是复杂解法的测试结果,下面上简单解法,用空间换时间的思想,添加一个标记数组用来标记

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int a[10][10];
	int b[10][10];
	int i,j,n,count;int t;int x,y;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			b[i][j]=0;
	count=0;
	x=0;y=0;
	t=1;
	while(count<n*n)
	{
		while(y<n&&b[x][y]==0)
		{
			a[x][y]=t;
			b[x][y]=1;
			t++;y++;count++;
		}
		y--;x++;
		while(x<n&&b[x][y]==0)
		{
			a[x][y]=t;
			b[x][y]=1;
			t++;x++;count++;
		}
		x--;y--;
		while(y>=0&&b[x][y]==0)
		{
			a[x][y]=t;
			b[x][y]=1;
			t++;y--;count++;
		}
		y++;x--;
		while(x>=0&&b[x][y]==0)
		{
			a[x][y]=t;
			b[x][y]=1;
			t++;x--;count++;
		}
		x++;y++;
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			printf("%3d",a[i][j]);
		}
		if(i!=n-1)
		printf("\n");
	}
		
		
	return 0;
	
}
PTA 7-9 螺旋方阵(20 分)简便解法与复杂解法

果然,简单解法占用内存稍多一些,不过都在可控范围之内,代码实现会比较容易