AOJ 0234 Aizu Buried Treasure
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0234
なんか変なところでミスってデバッグにかなり時間が取られました。(nvis>>ny&1とすべきところをnvis>>nx&1としていたり、=とすべきところを==にしていたり)
遅いですが、一応通りました。
現在の位置と、所持している酸素の量、現在の高さでの掘った場所を状態にしてBFSしました。
int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; typedef struct{ int x,y; int o,st; int cost; }state; int vis[10][10][1<<10][50]; int in[10][10]; main(){ int w,h; while(cin>>w>>h,w|h){ memset(vis,0,sizeof(vis)); rep(i,10)rep(j,10)rep(k,1<<10)rep(l,50)vis[i][j][k][l]=1<<28; int f,m,o; cin>>f>>m>>o; rep(i,h)rep(j,w)cin>>in[i][j]; queue<state> Q; state st; st.x=0; rep(i,w){ st.y=i; st.o=o-1; if(st.o<1)continue; if(in[0][i]<0){ st.cost=-in[0][i]; }else{ st.o+=in[0][i]; st.cost=0; } if(st.o>m)st.o=m; st.st=1<<i; if(st.cost>f || st.o<1)continue; Q.push(st); } while(!Q.empty()){ st=Q.front();Q.pop(); int cx=st.x,cy=st.y,cvis=st.st,cc=st.cost,co=st.o; if(vis[cx][cy][cvis][co]<=cc)continue; vis[cx][cy][cvis][co]=cc; rep(i,3){ int nx=cx+dx[i],ny=cy+dy[i]; int nc=cc; int no=co-1; int nvis=cvis; if(no<1)continue; if(nx<0 || h<=nx || ny<0 || w<=ny)continue; if((dx[i]==0 && (nvis>>ny&1)==0) || dx[i]){ if(in[nx][ny]<0)nc-=in[nx][ny]; else no+=in[nx][ny]; if(no>m)no=m; } if(dx[i]==0)nvis=cvis|1<<ny; else nvis=1<<ny; if(nc>f)continue; if(vis[nx][ny][nvis][no]<=nc)continue; st.x=nx,st.y=ny,st.st=nvis,st.cost=nc,st.o=no; Q.push(st); } } int ans=f+1; rep(i,w)rep(j,1<<w)rep(k,m)ans=min(ans,vis[h-1][i][j][k+1]); if(ans==f+1)cout<<"NA"<<endl; else cout<<ans<<endl; } }