# 有没有大佬解答一下，这题按模拟来DFS只能过两个点（没想到拓扑序QAQ）

chk(x,y) 是检验以 (x,y) 为左上角的矩形是否存在

#include<bits/stdc++.h>
using namespace std;
template<class _T> inline void read(_T &_a)
{
bool f=0;char _ch=getchar();_a=0;
while(_ch<'0'||_ch>'9'){if(_ch=='-')f=1;_ch=getchar();}
while(_ch>='0'&&_ch<='9'){_a=(_a<<3)+(_a<<1)-'0'+_ch;_ch=getchar();}
if(f) _a=-_a;
}

char mp[10001][10001],stk[10001];
bool vis[26];

bool chk(int x,int y)
{
int zuo=y,you=y,shang=x,xia=x;
for (register int i=zuo;i<m;++i)
if(mp[shang][i+1]=='.') break;
else if(mp[shang][i+1]==mp[shang][i] || vis[mp[shang][i]-'A']|| vis[mp[shang][i+1]-'A']) you=i+1;
else break;
for (register int i=shang;i<n;++i)
if(mp[i+1][zuo]=='.') break;
else if(mp[i+1][zuo]==mp[i][zuo] || vis[mp[i+1][zuo]-'A'] || vis[mp[i][zuo]-'A']) xia=i+1;
else break;
while(xia-shang>=2 && you-zuo>=2)
{
bool gn=true;
for (register int i=shang;i<xia;++i)
if(mp[i+1][you]=='.') {gn=false; --xia; break;}
else if(mp[i+1][you]!=mp[i][you] && !vis[mp[i+1][you]-'A'] && !vis[mp[i][you]-'A']) {gn=false; --xia; break;}
for (register int i=zuo;i<you&&gn;++i)
if(mp[xia][i+1]=='.') {gn=false; --you; break;}
else if(mp[xia][i+1]!=mp[xia][i] && !vis[mp[xia][i+1]-'A'] && !vis[mp[xia][i]-'A']) {gn=false; --you; break;}
if(gn) break;
}
if(xia-shang<2 || you-zuo<2) return false;
return vis[mp[x][y]-'A']=true;
}

int main()
{
for(register int i=1;i<=n;getchar(),++i)
for (register int v=1;v<=m;++v)
mp[i][v]=getchar();
bool flag=true;
while(flag)
{
bool flag2=true; flag=false;
for (register int i=1;i<=n&&flag2;++i)
for (register int v=1;v<=m&&flag2;++v)
if(mp[i][v]!='.' && !vis[mp[i][v]-'A'] && chk(i,v))
}
return 0;
}

ID
1030

5

(无)

1056

374

35%