POJ 1270 Following Orders
問題
変数の集合と、変数の大小関係が与えられる。
大小関係を全て満たすような、変数の順序を全て、辞書順に出力せよ。
制約条件
変数の数≦20
制約条件≦50
答えの数≦500
方針
再帰により全探索する。
新しい文字を末尾に追加するとき、それよりも大きい変数が以前にあったらその時点で探索を打ち切る。
ソースコード
int n,m; char var[26],small[50],big[50]; char in[500],ans[27]; bool use[26]; void rec(int c){ if(c==n){ puts(ans); return; } rep(i,n)if(!use[i]){ rep(k,m)if(small[k]==var[i]) rep(j,c)if(big[k]==ans[j])goto FAIL; use[i]=1; ans[c]=var[i]; rec(c+1); use[i]=0; FAIL:; } } int main() { while(gets(in)){ n=m=0; for(int i=0;in[i];i++)if('a'<=in[i]&&in[i]<='z')var[n++]=in[i]; gets(in); bool f=0; for(int i=0;in[i];i++)if('a'<=in[i]&&in[i]<='z'){ if(f)big[m++]=in[i]; else small[m]=in[i]; f^=1; } sort(var,var+n); memset(ans,0,sizeof(ans)); rec(0); puts(""); } return 0; }