xxx
2025-02-06 16:43:59
发布于：上海
11阅读
0回复
0点赞
#include<iostream>//需检验
#include<vector>//c,short改int样例就过了
#include<queue>//rnmd scanf
#include<array>//什么 $scanf$ 魅力时刻 QAQ。
int t,n;char str[101][101],now,pre;std::array<std::vector<short>,26>s;
std::array<short,26>in,vis;
void bfs(){
int tmp=0;
std::queue<int>q;
for(int i=0;i<26;++i)if(vis[i]){
++tmp;
if(!in[i])q.push(i);
}
std::vector<int> ans;
while (!q.empty()) {
int u=q.front();q.pop();
ans.push_back(u);
for(int v:s[u]){
--in[v];
if(!in[v])q.push(v);
}
}
if(ans.size() == tmp){
for(int i=ans.size();i--;)printf("%c",ans[i]+'a');
for(int i(0);i<26;++i)if(!vis[i])printf("%c",i+'a');
puts("");
}
else puts("Impossible");
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i(0);i<n;++i)scanf("%s",str[i]);
for(int i(1);i<n;++i)for(int j(0);str[i-1][j]&&str[i][j];++j){
if(str[i][j+1]==0&&str[i-1][j+1]!=0){
puts("Impossible");
goto nxt;
}
if(str[i-1][j]!=str[i][j]){
int t=str[i][j]-'a',l=str[i-1][j]-'a';
s[t].push_back(l),++in[l];
vis[t]=vis[l]=1;
break;
}
}
bfs();
nxt:in.fill(0);s.fill(std::vector<short>());vis.fill(0);
}
return 0;
}
有帮助，赞一个