首页 > 代码库 > poj 2530 Tetris Alphabet 拓扑排序
poj 2530 Tetris Alphabet 拓扑排序
题意:
给一个俄罗斯方块的游戏截图,其中每个输入块都用字母A-Z标志出,求输入块的字典序最小的输入顺序。
分析:
即求字典序最小的拓扑序。
代码:
//poj 2530 //sep9 #include <iostream> using namespace std; char map[54][32]; int g[32][32]; int d[32]; int vis[32]; int main() { int n; scanf("%d",&n); memset(g,0,sizeof(g)); memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); for(int i=0;i<n;++i) scanf("%s",map[i]); for(int i=0;i<n;++i) for(int j=0;j<20;++j) if(map[i][j]!='.'){ int u=map[i][j]-'A'; vis[u]=1; for(int k=0;k<i;++k) if(map[k][j]!='.'&&map[k][j]!=map[i][j]){ int v=map[k][j]-'A'; if(g[u][v]==0){ g[u][v]=1; ++d[v]; } } } int i,t; while(1){ t=-1; for(i=0;i<26;++i) if(vis[i]==1&&d[i]==0&&t==-1){ t=i; vis[i]=0; } if(t==-1) break; printf("%c",'A'+t); for(i=0;i<26;++i) if(g[t][i]==1&&vis[i]) --d[i]; } return 0; }
poj 2530 Tetris Alphabet 拓扑排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。