今日题目：icpc A

链接：登录—专业IT笔试面试备考平台_牛客网

来源：牛客网

题目描述

BaoBao the Witch is stuck in a maze with nnn rows and nnn columns, where the height of the cell in the iii-th row and the jjj-th column is hi,jh_{i,j}hi,j. To get out of the maze, BaoBao has to find a path which passes through each cell exactly once. Each time she can only move into the neighboring cell sharing a same edge with the current one. But as we know, BaoBao is super lazy, so every time when she climbs up (that is to say, moving from a cell with a smaller height to another with a larger height) her happiness value will decrease. As her helping hand, your task is to find a valid path so that when moving along the path, the number of times BaoBao climbs up will not be more than the number of times she climbs down.

More formally, you need to find a sequence (x1,y1),(x2,y2),⋯ ,(xn2,yn2)(x_1, y_1), (x_2, y_2), \cdots, (x_{n^2}, y_{n^2})(x1,y1),(x2,y2),⋯,(xn2,yn2) such that:

·For all 1≤i≤n21 \le i \le n^21≤i≤n2, 1≤xi,yi≤n 1 \le x_i, y_i \le n1≤xi,yi≤n;

·For all 1≤i,j≤n2,i≠j1 \le i, j \le n^2, i \neq j1≤i,j≤n2,i=j, (xi,yi)≠(xj,yj) (x_i, y_i) \neq (x_j, y_j)(xi,yi)=(xj,yj);

·For all 2≤i≤n22 \le i \le n^22≤i≤n2, ∣xi−xi−1∣+∣yi−yi−1∣=1|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1∣xi−xi−1∣+∣yi−yi−1∣=1;

·∑i=2n2[hxi−1,yi−1hxi,yi]\sum\limits_{i=2}^{n^2}{[h_{x_{i-1}, y_{i-1}} < h_{x_i, y_i}]} \le \sum\limits_{i=2}^{n^2}{[h_{x_{i-1}, y_{i-1}} > h_{x_i, y_i}]}i=2∑n2[hxi−1,yi−1hxi,yi], where [P][P][P] equals 111 when PPP is true, and equals 000 when it is false.

Additionally, you discover that the heights in all cells are a permutation of n2n^2n2, so you just need to output the height of each cell in a valid path.

输入描述:

There are multiple test cases. The first line of the input contains an integer T (1≤T≤1001 \le T \le 1001≤T≤100) indicating the number of test cases. For each test case:

The first line contains an integer nnn (2≤n≤642 \le n \le 642≤n≤64) indicating the size of the maze.

For the following nnn lines, the iii-th line contains nnn integers hi,1,hi,2,⋯,hi,n (1≤hi,j≤n21) where hi,jh_{i,j}hi,j indicates the height of the cell in the iii-th row and the jjj-th column. It's guaranteed that all integers in the input make up a permutation of n2.

输出描述:

For each test case output one line containing n2n^2n2 separated by a space indicating the heights of each cell in a valid path. If there are multiple valid answers you can output any of them. It's easy to prove that an answer always exists.

Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

题目分析

题目难度：⭐️⭐️

题目涉及算法：bfs，队列，暴力。

ps：有能力的小伙伴可以尝试优化自己的代码或者一题多解，这样能综合提升自己的算法能力

题解报告：

1.思路

如果符合条件直接输出，不符合就直接反着来就好。

2.代码

#include<bits/stdc++.h>
using namespace std;
int a[100][100],b[100*100];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cin>>a[i][j];
            }
        }
        int len=0,num=0,sum=0;
        for(int i=1;i<=n;i++)
        {
            if(i%2==0)
            {
                for(int j=n;j>=1;j--)
                {
                    b[++len] = a[i][j];
                }
            }
            else
            {
                for(int j=1;j<=n;j++)
                {
                    b[++len] = a[i][j];
                }
            }
        }
        for(int i=1;i<len;i++)
        {
            if(b[i]>b[i+1])
            {
                num++;
            }
            else if(b[i]<b[i+1])
            {
                sum++;
            }
        }
        if(sum<=num)
        {
            cout<<b[1];
            for(int i=2;i<=len;i++)
            {
                cout<<" "<<b[i];
            }
        }
        else
        {
            cout<<b[len];
            for(int i=len-1;i>=1;i--)
            {
                cout<<" "<<b[i];
            }
        }
        cout<<endl;
    }
  return 0;
}