PKU 2688 AOJ 1140 Cleaning Robot
http://poj.org/problem?id=2688
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1140
日本語あるのでそれ参照。
現在の位置と訪れた汚れた場所を保持して幅優先探索。ただ、AOJで通った物はそのままだとPKUで通らなかったので、scanfにしたり、無駄にキューに突っ込んだりしないようして高速化した。
int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; bool vis[20][20][1<<10]; typedef struct{ int x,y; int vis; int cost; }state; char in[22][22]; int durty[22][22]; main(){ int w,h; while(scanf("%d%d",&w,&h),w|h){ int sx,sy; int num=0; rep(i,h){ scanf("%s",in[i]); rep(j,w){ if(in[i][j]=='o'){ sx=i; sy=j; in[i][j]='.'; }else if(in[i][j]=='*'){ durty[i][j]=num++; } } } memset(vis,0,sizeof(vis)); queue<state> Q; state st={sx,sy,0,0}; Q.push(st); int ans=-1; while(!Q.empty()){ int cx=Q.front().x,cy=Q.front().y,cvis=Q.front().vis,cc=Q.front().cost; Q.pop(); if(vis[cx][cy][cvis])continue; vis[cx][cy][cvis]=true; if(cvis==(1<<num)-1){ ans=cc; break; } rep(i,4){ int nx=cx+dx[i],ny=cy+dy[i]; if(nx<0 || h<=nx || ny<0 || w<=ny || in[nx][ny]=='x')continue; int nvis=cvis; if(in[nx][ny]=='*')nvis|=1<<durty[nx][ny]; if(vis[nx][ny][nvis])continue; st.x=nx; st.y=ny; st.vis=nvis; st.cost=cc+1; Q.push(st); } } cout<<ans<<endl; } }