- 重叠的方框
- 2018-11-05 18:33:48 @
思路是每次找到一个完整的矩形,压入栈内。完整的矩形上不能有“.”,但是可以出现已经出现过的矩形字母。
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;
}
int n,m,head;
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()
{
read(n); read(m);
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))
{stk[++head]=mp[i][v]; flag2=false; flag=true;}
}
while(head) printf("%c",stk[head--]);
return 0;
}
0 条评论
目前还没有评论...