小欧的美丽矩阵

[题目链接](https://www.nowcoder.com/practice/c78fcff464f34fe5a6d5cfe5c43842d7)

思路

给定一个 $2 \times 2$ 的矩阵，判断能否通过若干次顺时针旋转使其变为"美丽矩阵"。

美丽矩阵的条件

矩阵 $\begin{bmatrix} a & b \\ c & d \end{bmatrix}$ 是美丽的，当且仅当：

每行递增： $a < b$ ， $c < d$
每列递增： $a < c$ ， $b < d$

即左上角最小，右下角最大，且行列均严格递增。

旋转变换

一次顺时针旋转将 $\begin{bmatrix} a & b \\ c & d \end{bmatrix}$ 变为 $\begin{bmatrix} c & a \\ d & b \end{bmatrix}$ 。

旋转 4 次回到原矩阵，所以最多只需要检查 4 种状态（旋转 0、1、2、3 次）。

做法

枚举 0~3 次旋转，每次检查当前矩阵是否满足美丽条件。如果任意一次满足则输出 Yes，否则输出 No。

由于矩阵大小固定为 $2 \times 2$ ，每组数据的时间开销是常数级别的。

代码

C++
Java

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

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int a[4];
        for (int i = 0; i < 4; i++) scanf("%d", &a[i]);
        // 矩阵: [[a[0], a[1]], [a[2], a[3]]]
        bool ok = false;
        for (int r = 0; r < 4; r++) {
            if (a[0] < a[1] && a[2] < a[3] && a[0] < a[2] && a[1] < a[3]) {
                ok = true;
                break;
            }
            // 顺时针旋转: [[a,b],[c,d]] -> [[c,a],[d,b]]
            int tmp = a[0];
            a[0] = a[2];
            a[2] = a[3];
            a[3] = a[1];
            a[1] = tmp;
        }
        puts(ok ? "Yes" : "No");
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            int[] a = new int[4];
            for (int i = 0; i < 4; i++) a[i] = sc.nextInt();
            boolean ok = false;
            for (int r = 0; r < 4; r++) {
                if (a[0] < a[1] && a[2] < a[3] && a[0] < a[2] && a[1] < a[3]) {
                    ok = true;
                    break;
                }
                // 顺时针旋转
                int tmp = a[0];
                a[0] = a[2];
                a[2] = a[3];
                a[3] = a[1];
                a[1] = tmp;
            }
            sb.append(ok ? "Yes" : "No").append('\n');
        }
        System.out.print(sb);
    }
}

复杂度分析

时间复杂度： $O(T)$ ，其中 $T$ 为测试组数。每组数据只需常数次操作。
空间复杂度： $O(1)$ 。