CF1185E Polycarp and Snakes 题解
正难则反，考虑后涂色的不会被先涂色的覆盖，因此可以到序求解。
具体的，先找出输入矩阵中字典序最大的字母，从这个字母开始倒序枚举。
对于每一个字母，有出现过和没有出现过两种情况，如果没有出现过，直接在一个比它大的位置涂色一格就可以了（这一格将被覆盖，等于没涂），实现时可以直接填充为最后一个字母的第一格。如果出现过，判断它是否合法：首先判断出这个字母出现的所有位置是否都在同一行或同一列，再判断出现顺序是否连续（注意到如果之后有字母占有一个位置，那么它就不影响连续性，可以先涂上再覆盖），如果不合法直接输出无解，否则存入答案数组。
最后将答案数组倒序输出就行了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct point{
int x,y;
point(){}
point(int xx,int yy){
x=xx,y=yy;
}
friend bool operator < (point __,point _){
// return __.x+__.y<_.x+_.y;
return __.x==_.x?__.y<_.y:__.x<_.x;
}
};
struct answer{
point p1,p2;
};
vector<point>p[200];
map<point,bool>vis;
int n,m,sum;
char c,mx;
vector<answer>ans;
bool check(char ch){
if(p[ch].size()==1){
return true;
}
point s=p[ch][0];
point e=p[ch][p[ch].size()-1];
int po=0;
if(s.x==e.x){
for(auto i:p[ch]){
if(i.x!=s.x){
return false;
}
}
for(int i=s.y;i<=e.y;i++){
if(i==p[ch][po].y){
po++;
}
else if(!vis[point(s.x,i)]){
return false;
}
}
}
else if(s.y==e.y){
for(auto i:p[ch]){
if(i.y!=s.y){
return false;
}
}
for(int i=s.x;i<=e.x;i++){
if(i==p[ch][po].x){
po++;
}
else if(!vis[point(i,s.y)]){
return false;
}
}
}
else{
return false;
}
return true;
}
void solve(){
for(int i='a';i<='z';i++){
p[i].clear();
}
vis.clear();
ans.clear();
sum=0,mx='a';
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c;
if(c!='.'){
p[c].push_back({i,j});
sum++;
mx=max(mx,c);
}
}
}
if(sum==0){
cout<<"YES\n0\n";
return;
}
for(int i=mx;i>='a';i--){
if(p[i].size()==0){
ans.push_back({p[mx][0],p[mx][0]});
continue;
}
if(!check(i)){
cout<<"NO"<<endl;
return;
}
ans.push_back({p[i][0],p[i][p[i].size()-1]});
for(auto j:p[i]){
vis[j]=1;
}
}
cout<<"YES"<<endl;
cout<<ans.size()<<endl;
for(int i=ans.size()-1;i>=0;i--){
cout<<ans[i].p1.x<<" "<<ans[i].p1.y<<" "<<ans[i].p2.x<<" "<<ans[i].p2.y<<endl;
}
}
signed main(){
#ifdef USE_FILE_IO
freopen("code.in","r",stdin);
cerr<<"[File IO]"<<endl;
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}