题目描述
小 X 是 C 城著名的考古学家。一日,他被重金聘请调查一座荒漠中的宫殿。
宫殿大门紧闭,但这难不倒聪明的小X。他在隐蔽处发现了两个数字正方形:
小 X 略加思索便发现了其中的奥妙:把数字从小到大依次填入正方形中,每次填最外面的一圈;每一圈从左上角开始,按照顺时针、逆时针、顺时针……的顺序填。
作为小 X 的助手,他希望你帮助他以相同的规律填上旁边 n*n 的空白方阵。
这里方阵是数字正方形的简称,通常用二维数组来存放其中的数字。
输入
输入数据仅有一行,包含一个正整数 n,表示方阵的边长,即每行每列有多少个数。
输出
输出仅 n 行,每行 n 个正整数,相邻两数之间严格用一个空格隔开。
样例输入
6
样例输出
1 2 3 4 5 6
20 21 32 31 30 7
19 22 33 34 29 8
18 23 36 35 28 9
17 24 25 26 27 10
16 15 14 13 12 11
提示
本题共有 10 个测试点,每个测试点 10 分
对于测试点 1 :n=1; 对于测试点 2 :n=2
对于测试点 3 :n=3; 对于测试点 4 :n=4
对于测试点 5 :n=7; 对于测试点 6 :n=8
对于测试点 7 :n=10;对于测试点 8 :n=15
对于测试点 9 :n=25;对于测试点 10:n=50
思路
直接模拟填数然后移动
最外层会填数并移动n-1次 然后转向(顺时针)
以上步骤会重复4次
到了倒数第二层会填数并移动n-2次 然后转向(逆时针)
以此类推…
注意:
①转向 这个操作到了第四次,回多走,要回退一步再转向
②当n是奇数时,最中间的数会没有填,要补上
AC代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int map[60][60],n,num = 1,x = 1,y = 1;
int dx_a[4] = {0,1,0,-1}; //右 下 左 上
int dy_a[4] = {1,0,-1,0};
int dx_b[4] = {1,0,-1,0};
int dy_b[4] = {0,1,0,-1};
int main()
{
cin >> n;
for(int k = n-1,flag = 0; k > 0; k -= 2,flag = (flag+1)%2)
{
for(int i = 0; i < 4; i++)
{
for(int j = 1; j <= k; j++)
{
map[x][y] = num;
num++;
if(flag) // 0顺时针
{
x += dx_b[i];
y += dy_b[i];
}
else
{
x += dx_a[i];
y += dy_a[i];
}
}
}
if(flag)
{
x -= dx_b[3];
y -= dy_b[3];
x += dx_b[0];
y += dy_b[0];
}
else
{
x -= dx_a[3];
y -= dy_a[3];
x += dx_a[0];
y += dy_a[0];
}
}
if(n%2!=0)
{
map[(n+1)/2][(n+1)/2] = num;
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
cout << map[i][j] << " ";
}
cout << endl;
}
return 0;
}