algospot - wordchain

Algorithm/알고스팟

algospot - wordchain

jhg0406 2020. 1. 10. 15:08

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

//Algospot - WORDCHAIN
 
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
int N;
int sidx, eidx, tidx;
bool c_flag;
vector<int> icount, ocount;
vector<stack<string>> adj;
stack<string> ans;
 
void init()
{
    ans = stack<string>();
    sidx = eidx = -50;
    icount = ocount = vector<int>(26, 0);
    adj = vector<stack<string>>(26);
    cin >> N;
    string s;
    for (int i = 0; i < N; i++)
    {
        cin >> s;
        tidx = s[0]-'a';
        adj[s[0] - 'a'].push(s);
        ++icount[s[0] - 'a'];
        ++ocount[s[s.size() - 1] - 'a'];
    }
    for (int i = 0; i < 26; i++)
    {
        if (sidx + eidx >= -100)
        {
            if (icount[i] > ocount[i])
            {
                if (sidx == -50)
                    sidx = i;
                else
                    sidx = -1000;
            }
            else if(icount[i] < ocount[i])
            {
                if(eidx == -50)
                    eidx = i;
                else
                   eidx = -1000;
            }
        }
    }
    if(sidx + eidx >0 || sidx +eidx == -100)
        c_flag = true;
    else
        c_flag = false;
}
 
void dfs(int here)
{
    int there;
    string s;
    while(!adj[here].empty())
    {
        --N;
        s = adj[here].top(); adj[here].pop();
        there = s[s.size()-1];
        dfs(there-'a');
        ans.push(s);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int C;
    cin >> C;
    for (int t_num = 0; t_num < C; t_num++)
    {
        init();
        if(c_flag)
        {
            if(sidx == -50) sidx = tidx;
            dfs(sidx);
            if(N)
                c_flag = false;
        }
        if(c_flag)
            while(!ans.empty()){
                cout << ans.top() << " ";
                ans.pop();
            }
        else
            cout << "IMPOSSIBLE";
        cout << endl;
    }
}
Colored by Color Scripter

cs

 

https://algospot.com/judge/problem/read/WORDCHAIN

algospot.com :: WORDCHAIN

단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 말한 단어의 마지막 글자와 같아야 합니다. 단어 제한 끝말잇기는 일반적인 끝말잇기와 달리 사용할 수 있는 단어의 종류가 게임 시작 전에 미리 정해져 있으며, 한 단어를 두 번 사용할 수 없습니다. 단어 제한 끝말잇기에서 사용할 수 있는 단어들의 목록이 주어질 때, 단어들

algospot.com

Wordchain한붓그리기인 오일러서킷/오일러트레일 문제입니다.
각 단어를 정점으로 하는 그래프가 아닌 각 단어를 간선으로 하고 시작/끝 알파벳을 정점으로 하는 그래프를 이용합니다.
 