ccf 201412 02 (Z字形扫描)
作者:
Accepting
,
2020-08-06 19:40:27
,
所有人可见
,
阅读 566
鄙人不才,此中鄙陋甚多,望海涵!!!
这道题目刨析之后就会发现它其实是按照对角线来输出的,在一个n*n
的矩阵中,共有2*n+1
条对角线,所以我们在读入的时候可以观察每个数的横纵坐标之和来判断它在哪条斜线上,研究后我们就会发现,当横纵坐标之和为偶数的对角线是要从下往上输出,反之是要从上往下输出,这样的话我们不难想到双端队列,可以将偶数的每次push_front()
,反之push_back()
,最终遍历双端队列去得到结果即可!(注意,其实双端队列的常数复杂度还是比较大的,因此这个方法在代码量上应该是最优的,但在运行时间上还是有点慢,当然也可以手动模拟双端队列,但是由于这道题目的数据少,我们直接利用STL自带双端队列即可)
#include<iostream>
#include<deque>
using namespace std;
const int N=1010;
deque<int> a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int x;
scanf("%d",&x);
if(!((i+j)&1)) a[i+j].push_front(x);
else a[i+j].push_back(x);
}
for(int i=2;i<=2*n;i++) for(auto x:a[i]) printf("%d ",x);
return 0;
}
持续更新中,更新完历年1,2就会更新4,5!