首页 > 代码库 > poj1128拓扑排序
poj1128拓扑排序
按照硕神的说法,以无比丑的姿势 建了个图。然后裸搞 拓扑排序
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;struct Node{ int l;int r;int up;int down;}node[1111111];int sum;const int INF=0xfffffff;int Map[100][100];int out[100];int in[100];int path[1000];int vis[1000];int vis1[1111];void dfs(int cnt){ if(cnt==sum){ for(int i =0 ;i< sum;i++) printf("%c",path[i]+‘A‘); cout<<endl; return ; } for(int i =0 ;i<26;i++){ if(vis[i]&&out[i]==0&&!vis1[i]){ vis1[i]=1; path[cnt]=i; for(int j=0;j<26;j++){ if(Map[j][i]) out[j]--; } dfs(cnt+1); for(int j=0;j<26;j++){ if(Map[j][i]) out[j]++; } vis1[i]=0; } }}int main(){ int n,m; char str[100][1111]; while( cin>>n>>m){ sum=0; memset(Map,0,sizeof(Map)); memset(out,0,sizeof(out)); memset(in, 0,sizeof(in)); memset(vis,0,sizeof(vis)); memset(vis1,0,sizeof(vis1)); for(int i = 0 ;i< 100;i++){ node[i].down=INF;node[i].up=0;node[i].r=0;node[i].l=INF; } for(int i =0 ;i<n;i++) scanf("%s",str[i]); for(int i =0 ;i<n;i++){ for(int j=0;j<m;j++){ if(str[i][j]>‘Z‘||str[i][j]<‘A‘)continue; int t=str[i][j]-‘A‘; if(i<node[t].down) node[t].down = i; if(i>node[t].up) node[t].up=i; if(j>node[t].r) node[t].r= j; if(j<node[t].l) node[t].l=j; vis[t]=1; } } for(int i= 0;i<26;i++) if(vis[i]) sum++; for(int t=0;t<26;t++){ if(!vis[t]) continue; int l=node[t].l;int r=node[t].r;int up=node[t].up;int down = node[t].down; int i = down; for(int j = l;j<=r;j++){ if(str[i][j]>‘Z‘||str[i][j]<‘A‘)continue; int cc=str[i][j]-‘A‘; if(cc!=t&&!Map[cc][t]) { Map[cc][t]= 1; out[cc]++; } } i=up; for(int j =l;j<=r;j++){ if(str[i][j]>‘Z‘||str[i][j]<‘A‘)continue; int cc=str[i][j]-‘A‘; if(cc!=t&&!Map[cc][t]) { Map[cc][t]= 1; out[cc]++; } } int j= l; for(int i = down+1;i<up;i++){ if(str[i][j]>‘Z‘||str[i][j]<‘A‘)continue; int cc=str[i][j]-‘A‘; if(cc!=t&&!Map[cc][t]) { Map[cc][t]= 1; out[cc]++; } } j= r; for(int i = down+1;i<up;i++){ if(str[i ][j]>‘Z‘||str[i][j]<‘A‘)continue; int cc=str[i][j]-‘A‘; if(cc!=t&&!Map[cc][t]) { Map[cc][t]= 1; out[cc]++; } } } dfs(0); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。