RE求助
  • 板块P1127 词链
  • 楼主AHXBXA
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/12/19 15:31
  • 上次更新2023/10/28 14:04:55
查看原帖
RE求助
324709
AHXBXA楼主2021/12/19 15:31
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
string S[1030];
bool s[30][1030];
int n = 0;
string read()
{
    char a;
    string s = "";
    a = getchar();
    while (a <= 'z' && a >= 'a')
    {
        s += a;
        a = getchar();
    }
    return s;
}
struct point
{
    bool exit = false;
    vector<string> Next;
    int in = 0;
} P[30];
bool pass = false;
string dfs(int now, string now_result, int now_total)
{
    if (now_total == n)
    {
        pass = true;
        return now_result;
    }
    for (int i = 0; i < P[now].Next.size(); i++)
    {
        if (s[now][i] && P[P[now].Next[i][P[now].Next[i].length() - 1] - 'a'].in != 0)
        {
            P[P[now].Next[i][P[now].Next[i].length() - 1] - 'a'].in--;
            now_result += P[now].Next[i] + ".";
            s[now][i] = false;
            string temp = dfs(P[now].Next[i][P[now].Next[i].length() - 1] - 'a', now_result, now_total + 1);
            if (pass)
            {
                return temp;
            }
            s[now][i] = true;
            P[P[now].Next[i][P[now].Next[i].length() - 1] - 'a'].in++;
            now_result.erase(now_result.length() - P[now].Next[i].length() - 1, P[now].Next[i].length() + 1);
        }
    }
    return "***";
}
int main()
{
    scanf("%d\n", &n);
    memset(S, 0, sizeof(S));
    memset(s, true, sizeof(s));
    for (int i = 0; i < n; i++)
    {
        string temp = read();
        S[i] = temp;
    }
    sort(S, S + n);
    for (int i = 0; i < n; i++)
    {
        if (!P[S[i][0] - 'a'].exit)
            P[S[i][0] - 'a'].exit = true;
        P[S[i][0] - 'a'].Next.push_back(S[i]);
        P[S[i][S[i].length() - 1] - 'a'].in++;
        P[S[i][S[i].length() - 1] - 'a'].exit = true;
    }
    int start = -1;
    int end = -1;
    int max = 0;
    bool s = false;
    for (int i = 0; i < 26; i++)
    {
        if (P[i].exit)
        {
            max = max > i ? max : i;
            s = false;
            if (P[i].in == P[i].Next.size())
                s = true;
            if (!s)
                break;
        }
    }
    if (s)
    {
        start = S[0][0] - 'a';
        end = max;
    }
    else
        for (int i = 0; i < 26; i++)
        {
            if (P[i].exit)
            {
                if (P[i].in == P[i].Next.size())
                    continue;
                else if (P[i].in == P[i].Next.size() - 1)
                {
                    if (start != -1)
                    {
                        printf("***");
                        return 0;
                    }
                    start = i;
                }
                else if (P[i].in == P[i].Next.size() + 1)
                {
                    if (end != -1)
                    {
                        printf("***");
                        return 0;
                    }
                    end = i;
                }
                else
                {
                    printf("***");
                    return 0;
                }
            }
        }
    if (start != -1 && end != -1)
    {
        string result = dfs(start, "", 0);
        if (result != "***")
            result.erase(result.length() - 1, 1);
        printf("%s", result.c_str());
    }
    return 0;
}
2021/12/19 15:31
加载中...