当前位置: 代码迷 >> 综合 >> poj 2530 Tetris Alphabet 拓扑排序
  详细解决方案

poj 2530 Tetris Alphabet 拓扑排序

热度:85   发布时间:2024-01-19 06:05:00.0

题意:

给一个俄罗斯方块的游戏截图,其中每个输入块都用字母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;	
}