266
poj 1128 Frame Stacking 拓撲
和上一題一樣的一個覆蓋問題，這個要給出全部可能序列，所以就有個遞歸過程
用了很多stl，本來以為會TLE，結果0ms就過了，還有很大的優化空間，比如可以把拓撲的dfs和入度為0結合起來就可以少很多重複搜索的情況。
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int h,w,map[32][32],cnt;
char ans[100];//暫存排序
vector<int> cover[27];//覆蓋關係
vector<string> Ans;//全部排序
int l[27],r[27],u[27],d[27],in[27],k;//最左最右最上最下，和記錄是否在排序中
bool init()
{
int i,j,k;
if(scanf("%d%d",&h,&w)!=2)return 0;
memset(l,127,sizeof(l));memset(u,127,sizeof(u));//127隻是個大數
memset(r,-1,sizeof(r));memset(d,-1,sizeof(d));
Ans.clear();cnt=0;
for(i=0;i<27;i++)cover[i].clear();
for(i=0;i<h;i++)
{
getchar();
for(j=0;j<w;j++)
{
k=getchar()-'A';
map[i][j]=k;
if(k<0)continue;
l[k]=min(l[k],j);r[k]=max(r[k],j);
u[k]=min(u[k],i);d[k]=max(d[k],i);
}
}
return 1;
}
bool build()//尋找覆蓋關係
{
int i,j;
for(i=0;i<26;i++)
{
if(r[i]<0)continue;
cnt++;
for(j=l[i];j<=r[i];j++)
{
if(map[u[i]][j]!=i)cover[i].push_back(map[u[i]][j]);//這一步可能重複添加很多次……但是n較少可以接受，最好優化
if(map[d[i]][j]!=i)cover[i].push_back(map[d[i]][j]);
}
for(j=u[i]+1;j<d[i];j++)
{
if(map[j][l[i]]!=i)cover[i].push_back(map[j][l[i]]);
if(map[j][r[i]]!=i)cover[i].push_back(map[j][r[i]]);
}
}
k=cnt-1;ans[cnt]='\0';
return 1;
}
bool dfs(int v)
{
in[v]=1;
for(int u,i=0;i<cover[v].size();i++)
{
u=cover[v][i];
if(!in[u])dfs(u);//因為數據保證，不需判斷環
}
ans[k--]=v+'A';
return 1;
}
void check()
{
int t=k;
int a[35];
memcpy(a,in,sizeof(a));
for(int i=0;i<26;i++)
{
if(r[i]<0||in[i])continue;
if(!dfs(i))return;
if(k<0)Ans.push_back(ans);//加入，會有重複，可優化
else check();
memcpy(in,a,sizeof(a));//恢複狀態
k=t;
}
}
int main()
{
while(init())
{
build();
memset(in,0,sizeof(in));
check();
sort(Ans.begin(),Ans.end());//字典序
int len=unique(Ans.begin(),Ans.end())-Ans.begin();//去重
for(int i=0;i<len;i++) cout<<Ans[i]<<endl;
}
}
最後更新：2017-04-02 22:15:46