Link
这里我们默认相邻为四连通。
一个+要从它相邻的格子里任选两个.。
一个*要从它左右/上下的格子中各选一个.。
我们将+ or *（后文称为关键点）拆成两个点，并在这两个点之间连边。
如果这是+，那么两个点分别向周围的四个点中的.连边。
如果这是*，那么第一个点向左右的两个点中的.连边，第二个点向上下的两个点中的.连边。
然后我们求这个无向图的最大匹配。
不难发现对于一个关键点，要么两个点相互匹配（表示这个关键点不生成tromino），要么两个点分别与合法的.匹配（表示这个关键点生成tromino）。
因为我们求的是最大匹配，显然会让尽可能多的关键点与合法的.匹配。
这样我们求出来的方案就是使得tromino最多的方案，而且这个方案的合法性是显然的。
然后我们要给tromino染a~z，直接暴力对生成tromino的关键点判断其周围有哪些字母被选即可。
#include<queue>
#include<cctype>
#include<cstdio>
#include<vector>
#include<cstring>
#include<numeric>
const int N=107,M=20007,d[4][2]={0,1,0,-1,1,0,-1,0};
int cnt,id[N][N],px[M],py[M],vis[26],fa[M],col[M],mat[M],pre[M];char str[N][N];std::vector<int>e[M];std::queue<int>q;
int read(){int x;scanf("%d",&x);return x;}
void add(int u,int v){e[u].push_back(v),e[v].push_back(u);}
int find(int x){return x==fa[x]? x:fa[x]=find(fa[x]);}
int lca(int u,int v)
{
static int f[M],t;++t;
for(;f[u]^t;std::swap(u,v)) if(u) f[u]=t,u=find(pre[mat[u]]);
return u;
}
void blossum(int u,int v,int p){for(;find(u)^p;u=pre[v]) if(pre[u]=v,v=mat[u],fa[u]=fa[v]=p,col[v]==1) col[v]=2,q.push(v);}
void bfs(int s)
{
while(!q.empty()) q.pop();
memset(col+1,0,cnt<<2),std::iota(fa+1,fa+cnt+1,1),q.push(s),col[s]=2;
while(!q.empty())
{
int u=q.front(),p;q.pop();
for(int v:e[u])
if(!col[v])
{
col[v]=1,pre[v]=u,col[mat[v]]=2,q.push(mat[v]);
if(!mat[v])
{
while(u) u=mat[pre[v]],mat[v]=pre[v],mat[pre[v]]=v,v=u;
return ;
}
}
else if(col[v]==2) p=lca(u,v),blossum(u,v,p),blossum(v,u,p);
}
}
void work(int i,int j){for(int x,y,k=0;k<4;++k)if(islower(str[x=i+d[k][0]][y=j+d[k][1]]))vis[str[x][y]-'a']=1;}
int main()
{
int n=read(),m=read();
for(int i=1;i<=n;++i) scanf("%s",str[i]+1);
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) id[i][j]=++cnt,px[cnt]=i,py[cnt]=j,cnt+=str[i][j]!='.';
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(str[i][j]=='+')
{
for(int x,y,k=0;k<4;++k)if(str[x=i+d[k][0]][y=j+d[k][1]]=='.')add(id[i][j],id[x][y]),add(id[i][j]+1,id[x][y]);
add(id[i][j],id[i][j]+1);
}
else if(str[i][j]=='*')
{
for(int x,y,k=0;k<4;++k)if(str[x=i+d[k][0]][y=j+d[k][1]]=='.')add(id[i][j]+(k>1),id[x][y]);
add(id[i][j],id[i][j]+1);
}
for(int i=1;i<=cnt;++i) if(!mat[i]) bfs(i);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if((str[i][j]=='*'||str[i][j]=='+')&&mat[id[i][j]]&&mat[id[i][j]+1])
{
if(mat[id[i][j]]==id[i][j]+1) continue;
memset(vis,0,104),work(i,j),work(px[mat[id[i][j]]],py[mat[id[i][j]]]),work(px[mat[id[i][j]+1]],py[mat[id[i][j]+1]]);
for(int k=0;k<26;++k)if(!vis[k]){str[i][j]=str[px[mat[id[i][j]]]][py[mat[id[i][j]]]]=str[px[mat[id[i][j]+1]]][py[mat[id[i][j]+1]]]='a'+k;break;}
}
for(int i=1;i<=n;++i) puts(str[i]+1);
}