说明

该代码解决的问题是判断在给定的网格中，是否可以通过绘制若干条水平和垂直的粗线，将网格划分为若干个矩形，使得每个矩形内要么包含所有相同字母的实例，要么不包含任何字母。具体来说，给定每个字母的多个实例的坐标，需要判断是否存在一种划分方式，使得每个字母的所有实例都位于同一个矩形内，并且这些矩形之间没有重叠或相同的边界。

算法标签

• 几何处理
• 矩形合并
• 边界检查

解题思路

1. 输入处理：读取测试用例的数量，每个测试用例的字母种类数 k 和每个字母的实例数 p，以及每个字母实例的坐标。
2. 初始化边界：对于每个字母，初始化其左、右、上、下边界。左边界和上边界初始化为最大值，右边界和下边界初始化为最小值。
3. 计算边界：遍历每个字母的所有实例，更新其左、右、上、下边界，形成一个包含所有实例的最小矩形。
4. 矩形合并：对于每个字母的矩形，检查是否可以与其他字母的矩形合并。具体来说，如果当前矩形的边界与其他矩形的边界有重叠或包含关系，则调整当前矩形的边界以包含这些重叠部分。
5. 唯一性检查：检查所有字母的矩形是否唯一，即没有两个字母的矩形具有相同的左、右、上、下边界。如果有重复的矩形，则无法满足划分条件，输出 NO；否则输出 YES。

分析

• 边界计算：代码首先计算每个字母所有实例的最小包围矩形，这一步是正确的，因为它确保了所有实例都被包含在矩形内。
• 矩形合并：代码尝试通过调整矩形的边界来合并可能的重叠或相邻矩形。这一步的逻辑是，如果一个矩形的边界在另一个矩形的内部，则扩展当前矩形的边界以包含另一个矩形。这种合并方式可能并不总是正确的，因为它假设所有重叠的矩形都可以通过简单的边界调整来合并，而实际上可能需要更复杂的合并策略。
• 唯一性检查：最后检查所有矩形的唯一性，这是正确的，因为如果两个字母的矩形完全相同，则无法通过绘制线条将它们分开，从而导致无法满足题目条件。

实现步骤

1. 读取输入：读取测试用例的数量 n，然后逐个处理每个测试用例。
2. 初始化：对于每个字母，初始化其左、右、上、下边界。
3. 计算最小矩形：遍历每个字母的所有实例，更新其边界以形成最小包围矩形。
4. 合并矩形：对于每个字母的矩形，检查是否可以与其他字母的矩形合并，调整边界以包含重叠部分。
5. 检查唯一性：比较所有字母的矩形边界，确保没有重复的矩形。
6. 输出结果：根据唯一性检查的结果输出 YES 或 NO。

代码

/*相同的字母可以看成是一个长方形或正方形，
**那么每一个测试用例分别就有K个单独长方形了。
**每个长方形在满足一定的条件下进行扩充，最后得到的K个长方形，
**如果其中没有相同的就输出YES，否则就输出NO。
**C++版
*/
#include <iostream>
#define MAX 10001
#define min(a,b) a < b ? a : b
#define max(a,b) a < b ? b : a
 
using namespace std;
 
int l[27], r[27], u[27], d[27];
int k, p;//k表示the number of different letters, p 表示the number of instances of each letter.
 
int judge()
{
    int i, j;
    for(i = 0; i < k; i++)
    {
        for(j = i + 1; j < k; j++)
        {
            if(l[i] == l[j] && r[i] == r[j] && u[i] == u[j] && d[i] == d[j])
                return 0;
        }
    }
    return 1;
 
}
 
int main()
{
    int i, j, n;  //n表示测试组数
    int x, y;
    cin >> n;
    while(n--)
    {
        cin >> k >> p;
        for(i = 0; i < 27; i++)
        {
            l[i] = MAX; u[i] = MAX;
            r[i] = 0; d[i] = 0;
        }
        for(i = 0; i < k; i++)
        {
            for(j = 0; j < p; j++)
            {
                cin >> x >> y;
                l[i] = min(l[i], x - 1); r[i] = max(r[i], x);
                u[i] = min(u[i], y - 1); d[i] = max(d[i], y);
            }
        }
        //构造k个正方形
        for(i = 0; i < k; i++)
        {
            for(j = 0; j < k; j++)
            {
                if(i != j)
                {
                    if(l[i] < r[j] && l[i] > l[j])
                        l[i] = l[j];
                    if(r[i] < r[j] && r[i] > l[j])
                        r[i] = r[j];
                    if(u[i] < d[j] && u[i] > u[j])
                        u[i] = u[j];
                    if(d[i] < d[j] && d[i] > u[j])
                        d[i] = d[j];
                }
            }
        }
        if(judge())
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}