1401: [蓝桥杯2018决赛]整理玩具

约定不等于承诺〃 2022-12-15 12:53 144阅读 0赞

\*\*

# 1401: \[蓝桥杯2018决赛\]整理玩具 #

\*\*  
看了几个大佬的代码，感觉都具深奥，于是自己写了一个简洁的。

**原题如下：  
题目描述  
小明有一套玩具，一共包含NxM个部件。这些部件摆放在一个包含NxM个小格子的玩具盒中，每个小格子中恰好摆放一个部件。  
每一个部件上标记有一个0~9的整数，有可能有多个部件标记相同的整数。  
小明对玩具的摆放有特殊的要求：标记相同整数的部件必须摆在一起，组成一个矩形形状。  
如以下摆放是满足要求的：**

00022 
    00033 
    44444  
    
    12244 
    12244 
    12233
    
    01234 
    56789

**以下摆放不满足要求：**

11122 
    11122 
    33311
    
    111111 
    122221 
    122221 
    111111
    
    11122 
    11113 
    33333

**给出一种摆放方式，请你判断是否符合小明的要求。  
输入  
输入包含多组数据。  
第一行包含一个整数T，代表数据组数。 (1 <= T <= 10)  
以下包含T组数据。  
每组数据第一行包含两个整数N和M。 (1 <= N, M <= 10)  
以下包含N行M列的矩阵，代表摆放方式。  
输出  
对于每组数据，输出YES或者NO代表是否符合小明的要求。  
样例输入 Copy**

3  
    3 5  
    00022
    00033
    44444  
    3 5  
    11122
    11122
    33311
    2 5  
    01234
    56789

**样例输出**

YES
    NO
    YES

**解题思路：**  
有0~9这10个数字，找到 i 第一次和最后一次出现的位置，然后遍历一遍两个坐标之间的所有数字，如果有不同直接返回false ，最后输出。

**代码如下：**

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    
    char a[20][20];//存地图
    
    struct node
    {
        
        int x,y;
        node(int _x = 0, int _y = 0):x(_x),y(_y){
        }//初始化node这个数据类型
    };
    
    pair<node,node> p[15];//STL里面的一种数据结构
    
    int main()
    {
        
        int t;
        cin >> t;
        while(t--){
        
            int n,m;
            cin >> n >> m;
            int b[10] = {
        0};//判断 i 是不是第一次出现
            for(int i = 0; i <= 15; i++){
        //初始化 p 数组
                p[i].first.x = 0;
                p[i].first.y = 0;
                p[i].second.x = 0;
                p[i].second.y = 0;
            }
            bool ans = true;
            for(int i = 1; i <= n; i++){
        
                for(int j = 1; j <= m; j++){
        
                    cin >> a[i][j];
                    int flag = a[i][j] - '0';
                    if(b[flag] == 0){
        
                        p[flag].first.x = i;
                        p[flag].first.y = j;
                        b[flag] = 1;
                    }
                    else{
        
                        if(i > p[flag].second.x) p[flag].second.x = i;
                        if(j > p[flag].second.y) p[flag].second.y = j;
                    }
                }
            }
            for(int i = 0; i <= 9; i++){
        
                if(p[i].first.x == 0) continue;//地图中有没有 i 这个数字，判断p[i].first.y也可以。
                char op = a[p[i].first.x][p[i].first.y];
                for(int j = p[i].first.x; j <= p[i].second.x; j++){
        
                    for(int k = p[i].first.y; k <= p[i].second.y; k++){
        
                        if(a[j][k] != op){
        
                            ans = false;
                            goto exit;//不建议使用，但是懒得优化了。
                        }
                    }
                }
            }
            exit :
                if(ans) cout << "YES" << endl;
                else cout << "NO" << endl;
        }
    }