UVa-124, POJ-1270 : Following Orders
問題概要
文字がN(<20)以下ある。文字aは文字bより先に来る、という制約が複数個与えられる。全ての制約を満たすようなN文字の並び方を辞書順に全て出力する問題。出力結果はたかだか300種類以下であることが分かっている。
解法
辞書順といえばgreedy。基本的には先頭から辞書順に小さい方からdfsしていけばよい。ある状態から次にその文字が選べるかどうかは、残っている文字のなかで極小かどうかで判定できる。その判定も前処理でビット情報に詰め込んでおくとO(1)で判定できる。
acceptされたコード
計算量不明。入力読み込むの面倒くさい…。
#include <iostream> #include <cstdio> #include <sstream> #include <map> #include <cstring> #include <string> #include <algorithm> using namespace std; string line1, line2; const int MAX_N = 20; int N; char chs[MAX_N]; bool graph[MAX_N][MAX_N]; int parent_bit[MAX_N]; int path[MAX_N]; void print_path(){ for(int i=0; i<N; i++){ putchar(chs[path[i]]); } puts(""); } void dfs(int unused, int depth){ if(depth == N){ print_path(); return ; } for(int i=0; i<N; i++)if( (unused>>i)&1 ){ if( !(parent_bit[i] & unused) ){ path[depth] = i; dfs(unused & (~(1<<i)), depth+1); } } } void convert(){ memset(graph, false, sizeof(graph)); { string str; stringstream ss(line1); N = 0; while(ss >> str){ chs[N++] = str[0]; } sort(chs, chs+N); } { string s1, s2; stringstream ss(line2); while(ss >> s1 >> s2){ graph[lower_bound(chs, chs+N, s1[0]) - chs][lower_bound(chs, chs+N, s2[0]) - chs] = true; } } } void solve(){ convert(); for(int k=0; k<N; k++){ for(int i=0; i<N; i++){ for(int j=0; j<N; j++)if( graph[i][k] && graph[k][j] ){ graph[i][j] = true; } } } for(int i=0; i<N; i++){ int bit = 0; for(int j=0; j<N; j++)if( graph[j][i] ){ bit |= 1<<j; } parent_bit[i] = bit; } dfs((1<<N)-1, 0); } int main(){ bool first = false; while(getline(cin, line1)){ getline(cin, line2); if(first) puts(""); first = true; solve(); } return 0; }