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;
}