AOJ 1204

• 解法

最後のnクロックの状態と次にpipelineに入れられる仕事の番号を使って拡張ダイクストラをする。int dist[21][1<<20]とかやるとMLEするのでsetを使う。

//AOJ1204
#include <stdio.h>
#include <vector>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <set>
#define INF (1<<20)
#define W 10
using namespace std;
struct State{
	int time,next,line;
};
State makeS(int t,int nn,int l){
	State s;
	s.time=t,s.next=nn,s.line=l;
	return s;
}
bool operator < (const State &s,const State &t){
	return s.time>t.time;
}
int n;
int used[5];
char as[5][30];
int pi[30];
int check(int line){
	memset(used,0,sizeof(used));
	for(int i=n-1;0<=i;i--)
		if(line&(1<<i))
			used[pi[n-1-i]]++;
	for(int i=0;i<5;i++)
		if(1<used[i])
			return 0;
	return 1;
}
int main(){
	while(1){
		scanf("%d",&n);
		if(n==0)	break;
		for(int i=0;i<5;i++)scanf("%s",as[i]);
		for(int i=0;i<n;i++)for(int j=0;j<5;j++)if(as[j][i]=='X')pi[i]=j;
		int ans;
		priority_queue<State> que;
		set<pair<int,int> > se;
		que.push(makeS(0,0,0));
		se.insert(make_pair(0,0));
		while(!que.empty()){
			State s=que.top();que.pop();
			if(s.next==10&&s.line==1){ans=s.time;break;}
			int l=s.line>>1,ok=check(l);
			if(!ok)	continue;
			if(s.next==W){
				if(se.find(make_pair(W,l))==se.end()){
					se.insert(make_pair(W,l));
					que.push(makeS(s.time+1,W,l));
				}
			}else{
				int ll=l|(1<<(n-1));
				if(check(ll)){
					if(se.find(make_pair(s.next+1,ll))==se.end()){
						se.insert(make_pair(s.next+1,ll));
						que.push(makeS(s.time+1,s.next+1,ll));
					}
				}
				if(se.find(make_pair(s.next,l))==se.end()){
					se.insert(make_pair(s.next,l));
					que.push(makeS(s.time+1,s.next,l));
				}
			}
		}
		printf("%d\n",ans);
	}
}