LuoguP9656题解

luan341502 · 2023-09-25 12:44:04 · 题解

这题我们考虑随意找出一条路径，计算出题中所述的由上到下的次数和由下到上的次数，如果前者多直接输出，如果后者多倒序输出即可。

#include <bits/stdc++.h>
using namespace std;
int t;
int n,a[105][105];
vector<int> ans;
int main(){
    cin>>t;
    while(t--){
        ans.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=1;i<=n;i++){
            if(i&1){
                for(int j=1;j<=n;j++) ans.push_back(a[i][j]);
            }else{
                for(int j=n;j;j--) ans.push_back(a[i][j]);
            }
        }
        int cnt=0,cnt_=0,N=n*n;
        for(int i=0;i<N-1;i++){
            if(ans[i]>ans[i+1]) cnt++;
            else cnt_++;
        }
        if(cnt<cnt_) reverse(ans.begin(),ans.end());
        for(int i=0;i<N;i++){
            printf("%d ",ans[i]);
        }
        puts("");
    }
    return 0;
}