提交过五个点,用例已过,求助
查看原帖
提交过五个点,用例已过,求助
1347622
yh365t楼主2025/7/24 09:19
#include<bits/stdc++.h>
using namespace std;
long long h,w;
char a[31][31];
vector<char> zhonglei;
bool yilai[26][26];
bool shiyong[26];
vector<char> dangqian;
vector<string> jieguo;
void dfs(int shengyu)
{
    if(shengyu==0)
    {
        jieguo.push_back(string(dangqian.rbegin(),dangqian.rend()));
        return;
    }
    for(size_t i=0;i<zhonglei.size();i++)
    {
        char lei=zhonglei[i];
        if(!shiyong[i])
        {
            bool ke=true;
            for(size_t j=0;j<zhonglei.size();j++)
            {
                if(!shiyong[j]&&yilai[j][i])
                {
                    ke=false;
                    break;
                }
            }
            if(ke)
            {
                shiyong[i]=true;
                dangqian.push_back(lei);
                dfs(shengyu-1);
                dangqian.pop_back();
                shiyong[i]=false;
            }
        }
    }
}
int main()
{
    cin>>h>>w;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            cin>>a[i][j];
    bool cunzai[26]={false};
    for(long long i=1;i<=h;i++)
    {
        for(long long j=1;j<=w;j++)
        {
            if(a[i][j]!='.' && a[i][j]>='A' && a[i][j]<='Z') cunzai[a[i][j]-'A']=true;
        }
    }
    for(long long i=0;i<26;i++)
        if(cunzai[i]) zhonglei.push_back('A'+i);
    sort(zhonglei.begin(),zhonglei.end());
    memset(yilai,0,sizeof(yilai));
    memset(shiyong,0,sizeof(shiyong));
    for(long long i=0;i<zhonglei.size();i++)
    {
        char c=zhonglei[i];
        long long zuo=w,you=-1,shang=-1,xia=h;
        for(long long x=1;x<=h;x++)
        {
            for(long long y=1;y<=w;y++)
            {
                if(a[x][y]==c)
                {
                    zuo=min(zuo,y);
                    you=max(you,y);
                    shang=max(shang,x);
                    xia=min(xia,x);
                }
            }
        }
        for(long long x=xia;x<=shang;x++)
        {
            if(a[x][zuo]!=c && a[x][zuo]!='.' && a[x][zuo]>='A' && a[x][zuo]<='Z') yilai[a[x][zuo]-'A'][i]=true;
            if(a[x][you]!=c && a[x][you]!='.' && a[x][you]>='A' && a[x][you]<='Z') yilai[a[x][you]-'A'][i]=true;
        }
        for(long long y=zuo;y<=you;y++)
        {
            if(a[shang][y]!=c && a[shang][y]!='.' && a[shang][y]>='A' && a[shang][y]<='Z') yilai[a[shang][y]-'A'][i]=true;
            if(a[xia][y]!=c && a[xia][y]!='.' && a[xia][y]>='A' && a[xia][y]<='Z') yilai[a[xia][y]-'A'][i]=true;
        }
    } 
    dfs(zhonglei.size());
    sort(jieguo.begin(),jieguo.end());
    for(const auto& s:jieguo) cout<<s<<endl;
    return 0;
}
2025/7/24 09:19
加载中...