題意： 給出 h*w的圖形，要求字母框 自底向上的 疊加順序，有多種順序要按字典序全部輸出。 一開始沒想到思路，後面發現其實只要 構圖+拓撲排序 即可。。構圖為 如果 一個字母框 的邊界上有其他字母，那麼就 將 edge[][] 標記為1，同時 將該字母 的入度 in +1，而前面提到的其他字母 判斷入度 ，標記為 0, 進行 拓撲排序，即 首先 找到一個 入度為 0 的點，刪除，然後 將跟該頂點有邊 相連的 頂點入度 -1，繼續搜索。。 [cpp] #include<iostream> #include<cstdio> #include<string.h> #include<cstdlib> #include<algorithm> using namespace std; const int maxn=50; char map[maxn][maxn]; char str[maxn]; int edge[maxn][maxn]; int in[maxn]; bool vis[maxn]; int w,h,num; int index; struct lef_top{ int x,y; }lt[maxn]; struct rig_bot{ int x,y; }rb[maxn]; struct String{ char s[maxn]; }ans[1000]; int cmp(String a,String b){ return strcmp(a.s,b.s)<0; } void get_bound(){ memset(lt,0x3f,sizeof(lt)); memset(rb,-1,sizeof(rb)); //memset(flag,false,sizeof(flag)); for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ int tmp=map[i][j]-'A'; if(lt[tmp].x>i)lt[tmp].x=i; if(lt[tmp].y>j)lt[tmp].y=j; if(rb[tmp].x<i)rb[tmp].x=i; if(rb[tmp].y<j)rb[tmp].y=j; } } } void build_graph(){ num=0; for(int k=0;k<26;k++){ if(rb[k].x==-1)continue; num++; bool flag=true; for(int i=lt[k].x;i<=rb[k].x;i++){ for(int j=lt[k].y;j<=rb[k].y;j++){ if(i>lt[k].x && i<rb[k].x && j>lt[k].y && j<rb[k].y)continue; if(map[i][j]=='.')continue; int tmp=map[i][j]-'A'; if(!edge[tmp][k] && k!=tmp){ flag=false; edge[tmp][k]=1; //printf("%d %d\n",k,tmp); if(in[k]==-1)in[k]=1; else in[k]++; if(in[tmp]==-1){ in[tmp]=0; } } } } if(flag)in[k]=0; } } void DFS(char *s,int cnt){ //puts("+++++++++++++++++"); if(cnt==num){ for(int i=num-1,j=0;i>=0;i--){ ans[index].s[j++]=s[i]; //putchar(s[i]); } //putchar(10); ans[index++].s[num]=0; return; } for(int k=25;k>=0;k--){ if(in[k]==-1)continue; if(in[k]==0){ in[k]=-1; for(int i=0;i<26;i++)if(edge[k][i])in[i]--; s[cnt]=k+'A'; DFS(s,cnt+1); in[k]=0; for(int i=0;i<26;i++)if(edge[k][i])in[i]++; } } } int main(){ while(scanf("%d%d",&h,&w)==2){ for(int i=0;i<h;i++){ scanf("%s",map[i]); } www.2cto.com memset(edge,0,sizeof(edge)); memset(in,-1,sizeof(in)); memset(str,0,sizeof(str)); index=0; get_bound(); build_graph(); //printf("%d\n",num); //for(int i=0;i<26;i++){if(in[i]!=-1)printf("%d ",in[i]);}puts(""); DFS(str,0); sort(ans,ans+index,cmp); for(int i=0;i<index;i++)puts(ans[i].s); } }
