问题 111111111111111111111111111111

Question

描述

​ 小 A 有 n 种大小为 2×2 的瓷砖。瓷砖的每个单元格包含一个整数。每种类型瓷砖的数量都是无限的。

小 A 决定由给定的瓷砖在地面上铺一个大小为 m×m 的对称方阵。该对称方阵单元格上的数字必须是关于主对角线对称的，且该方阵的每个单元必须正好覆盖一个瓷砖单元格，并且所有瓷砖的侧边应与方阵的侧边始终保持平行，所有放置的瓷砖不能有叠加（当然方阵上所有单元格也必然全部由瓷砖覆盖），每块瓷砖都必须位于方阵内。

为方便更好地理解，可以参见样例解释中的图片。

主对角线对称的意思是：在方阵 s 中， i 表示行号， j 表示列号， i 和 j 都是从 1 到 m ，对于每个方格的位置 (i，j)， s[ i ] [ j ]=s[ j ] [ i ] 成立。

你的任务是确定小 A 是否可以用这些瓷砖构造一个大小为 m×m 的对称方阵。小 A 可以使用每种类型任意数量的瓷砖。

​ 请注意，她不能旋转瓷砖，只能按输入中的方向，将其平移到方阵中。

输入描述

第一行仅有一个整数 t (1≤t≤100) 表示测试数据的组数。

然后给出 t 组测试数据的具体信息。
对于每组测试数据：第一行包含两个整数 n 和 m (1≤m,n≤100) ；
接下来的 2n 行，每行包含两个整数，依次描述 n 中瓷砖的类型。
每两行描述一种瓷砖的类型，这两行的数字均为不超过 100 的正整数，依次为该种类型瓷砖左上角、右上角、左下角和右下角单元格上的数字。

输出描述

共有 t 行，依次输出每组测试数据的结果，对于每组测试数据，如果小 A 可以构造这种矩阵，输出 YES 。否则，输出 NO 。

用例输入 1

6
3 4
1 2
5 6
5 7
7 4
8 9
9 8
2 5
1 1
1 1
2 2
2 2
1 100
10 10
10 10
1 2
4 5
8 4
2 2
1 1
1 1
1 2
3 4
1 2
1 1
1 1

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

问题111111111111111111111111111111

小 A 想要铺一个大小为 m×m 的对称方阵，使用给定的瓷砖。我们可以使用动态规划来解决这个问题。

首先，我们可以将瓷砖的每个单元格看作是一个整数。然后，我们可以使用一个 m×m 的数组来表示对称方阵的每个单元格。

我们可以从数组的中心开始铺瓷砖。因为对称方阵是对称的，所以我们只需要考虑数组的上半部分。

我们可以使用一个变量 dp 来表示当前单元格可以使用的瓷砖的数量。dp[i][j] 表示当前单元格可以使用的瓷砖的数量。

我们可以使用以下公式来计算 dp[i][j]：

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

这个公式表示当前单元格可以使用的瓷砖的数量是上一个单元格可以使用的瓷砖的数量加 1。

最终，我们可以使用以下代码来解决这个问题：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minTile(int n, int m) {
    vector<vector<int>> dp(m+1, vector<int>(m+1, 0));
    for (int i = 1; i <= m; i++) {
        dp[i][0] = dp[0][i] = 1;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
        }
    }
    return dp[m][m];
}

int main() {
    int n, m;
    cin >> n >> m;
    cout << minTile(n, m) << endl;
    return 0;
}

这个代码可以正确地解决小 A 的问题。