RC-v6 拼瓷砖 2022 RoboCom 世界机器人开发者大赛-高职组（省赛）（肥肠煎蛋亿学就会ORZ

作者 陈越

单位 浙江大学

对照设计师给出的瓷砖拼接图案，请你统计一下需要多少种不同的瓷砖各多少块？

这里每块瓷砖都是单一颜色的正方形，每种颜色用一个 { 0-9，a-z，A-Z } 集合中的字符来表示。当设计图中有一方块颜色的面积为 L×L 时，我们将用一整块边长为 L 的正方形瓷砖来填充，而不会选用较小的同色瓷砖来拼接。此外，为了避免多解的情况，我们规定必须按照从上到下、从左到右的顺序贴瓷砖（参见样例解释），瓷砖不可重叠，并且要求每一步选用的瓷砖的面积尽可能大。

输入格式：

输入首先在第一行中给出两个不超过 103 的正整数 N 和 M，对应整面墙的高和宽。随后 N 行，每行给出 M 个字符，对应这一行的颜色分布。

输出格式：

首先在第一行输出不同瓷砖的种类数 K。随后 K 行，每行按格式

color = C; size = L; amount = T

输出一种瓷砖的信息。其中 C 是表示颜色的字符，L 是正方形的边长，T 是这种瓷砖需要的数量。

瓷砖按照其颜色的升序输出，同色的瓷砖按照其边长的升序输出。

输入样例：

6 6
aaadee
aacbee
deccda
caccbe
ddecbb
ddadbb

输出样例：

10
color = a; size = 1; amount = 4
color = a; size = 2; amount = 1
color = b; size = 1; amount = 2
color = b; size = 2; amount = 1
color = c; size = 1; amount = 3
color = c; size = 2; amount = 1
color = d; size = 1; amount = 4
color = d; size = 2; amount = 1
color = e; size = 1; amount = 3
color = e; size = 2; amount = 1

样例解释：

下图中的数字给出了贴瓷砖的顺序。

思路：

暴力模拟题，我们枚举每个未使用的点，二分寻找他的长度用map容器套用去记录，结束！！！！！Easy

代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define endl '\n'
const int N=1e4+5;
int n,m,k,t;
string s;
char a[N][N];
int vis[N][N];
map<char,map<int,int>>mp;
bool check(int x,int y,int num){//判断是否正确
    for(int i=x;i<x+num;i++){
        for(int j=y;j<y+num;j++){
            if(a[i][j]!=a[x][y]||vis[i][j]==1){
                return false;
            }
        }
    }
    return true;
}
void init(int x,int y,int num){
    for(int i=x;i<x+num;i++){
        for(int j=y;j<y+num;j++){
            vis[i][j]=1;
        }
    }
}
signed main() {
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){//枚举每个点
            if(vis[i][j]==0){//未被使用的点
                int l=1,r=min(n,m);//二分寻找长度
                while(l<r){
                    int mid=l+r+1>>1;
                    if(check(i,j,mid)){
                        l=mid;
                    }else r=mid-1;
                }
                init(i,j,l);
                mp[a[i][j]][l]++;
            }
        }
    }
    int num=0;
    for(auto it:mp){//跑一边计算
        for(auto i:it.second){
            num++;
        }
    }
    cout<<num<<endl;
    for(auto it:mp){//输出
        for(auto i:it.second){
            num++;
            cout<<"color = "<<it.first<<"; size = "<<i.first<<"; amount = "<<i.second<<endl;
        }
    }
    return 0;
}