有没有大佬解答一下,这题按模拟来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;
}

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 条评论

目前还没有评论...

信息

ID
1030
难度
5
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
1128
已通过
421
通过率
37%
被复制
10
上传者