Frame Stacking POJ - 1128
考察：拓扑排序 dfs
我觉得这道题最难的是理解题目...
这道题的字母是随机使用,不一定按顺序
思路：
我们先要在相片中找到各字母的边框.这里只能暴力查找.找到后遍历边框如果边框不是该字母,说明此字母是下面的边框.利用拓扑排序加边即可.
比较难的点是dfs遍历拓扑排序.本蒟蒻是看了别人的dfs才写出来.总之也和bfs差不多.我们必须先找到无根节点的结点.然后删去与它有关的边.再dfs寻找下一个无根的结点
1 #include <iostream> 2 using namespace std; 3 const int N = 910; 4 int hx,w; 5 bool vis[28]; 6 char mp[35][35]; 7 int h[N],e[N],ne[N],d[N],idx,n,m,xmp[35][35],cnt,path[28]; 8 struct alp{ 9 int x1,y1,x2,y2;10 bool use;11 }alpha[30];12 void inits()13 {14 fill(d,d N,0); fill(h,h N,-1);15 idx = 0; cnt = 0;16 fill(vis,vis 28,0);17 for(int i=1;i<=26;i ) alpha[i].use=0,alpha[i].x1=N,alpha[i].y1=N,alpha[i].y2=0,alpha[i].x2=0;18 }19 void add(int a,int b)20 {21 e[idx]=b,ne[idx]=h[a],h[a]=idx ; d[b] ;22 }23 void dfs(int k)24 {25 if(k==cnt){26 for(int i=0;i<k;i ) printf("%c",path[i] 'A'-1);27 printf("\n");28 }else{29 for(int i=1;i<=26;i ){30 if(!d[i]&&!vis[i]&&alpha[i].use)31 {32 path[k]=i;33 for(int j=h[i];j!=-1;j=ne[j]) d[e[j]]--;34 vis[i]=1;35 dfs(k 1);36 vis[i]=0;37 for(int j=h[i];j!=-1;j=ne[j]) d[e[j]] ;38 }39 }40 }41 }42 int main()43 {44 while(scanf("%d%d",&hx,&w)!=EOF)45 {46 inits();47 for(int i=1;i<=hx;i ){48 for(int j=1;j<=w;j ){49 cin>>mp[i][j];50 if(mp[i][j]!='.') {51 xmp[i][j]=mp[i][j]-'A' 1;52 alpha[xmp[i][j]].x1 = min(alpha[xmp[i][j]].x1,i);53 alpha[xmp[i][j]].y1 = min(alpha[xmp[i][j]].y1,j);54 alpha[xmp[i][j]].x2 = max(alpha[xmp[i][j]].x2,i);55 alpha[xmp[i][j]].y2 = max(alpha[xmp[i][j]].y2,j);56 alpha[xmp[i][j]].use = true;57 }58 }59 }//题目中每个字母都有可能出现,但不是按顺序的 60 for(int i=1;i<=26;i ){61 if(alpha[i].use){62 cnt ;63 for(int j=alpha[i].y1;j<=alpha[i].y2;j )64 if(xmp[alpha[i].x1][j]!=i) add(i,xmp[alpha[i].x1][j]);65 for(int j=alpha[i].y1;j<=alpha[i].y2;j )66 if(xmp[alpha[i].x2][j]!=i) add(i,xmp[alpha[i].x2][j]);67 for(int j=alpha[i].x1;j<=alpha[i].x2;j )68 if(xmp[j][alpha[i].y1]!=i) add(i,xmp[j][alpha[i].y1]);69 for(int j=alpha[i].x1;j<=alpha[i].x2;j )70 if(xmp[j][alpha[i].y2]!=i) add(i,xmp[j][alpha[i].y2]);71 }72 }73 dfs(0);74 } 75 return 0;76 }
赞 (0)