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