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