AOJ1140

Cleaning Robot

■問題
部屋の盤面が与えられ、スタートからすべての汚れたマスを通るように移動するときの最小距離を求めろ。

■解法
すべてのマスを通ってという巡回セールスマン問題のような問題だがスタートと各汚れとの距離は障害物があるため、先にBFSしてすべての2つの汚れまたは、スタート地点間の距離を求めておく。この時、辿りつけない組み合わせがあった場合は全てにたどり着くことが出来ないということがわかる。
あとは、その情報をもとにbitDPなどやるだけで求めることができる。

■ソース

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int w,h;
int b;
char c[33][33];

struct P{
  int x,y;
  P(int x,int y):x(x),y(y){}
};

vector<P> v;
int used[33][33];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int d[11][11];
int p;

int dp[1<<11][11];
int solve(int bit,int a){
  if(bit == (1<<p)-1) return 0;
  if(dp[bit][a] >= 0) return dp[bit][a];

  int ret = 1 << 28;
  for(int i = 1; i < p; i++){
    if(bit & 1 << i)continue;
    ret = min(ret,solve(bit | 1<<i,i) + d[a][i]);
  }
  return dp[bit][a] = ret;
}

int main(void){
  while(cin >> w >> h && w){
    v.clear();
    memset(c,-1,sizeof(c));
    v.push_back(P(0,0));
    p = 1;
    for(int i = 1; i <= h; i++){
      for(int j = 1; j <= w; j++){
	cin >> c[j][i];
	if(c[j][i] == 'o'){
	  c[j][i] = 0;
	  v[0].x = j;
	  v[0].y = i;
	}else if(c[j][i] == '*'){
	  c[j][i] = p;
	  p++;
	  v.push_back(P(j,i));
	}else if(c[j][i] == 'x'){
	  c[j][i] = -1;
	}
      }
    }

    memset(d,-1,sizeof(d));
    bool f = false;
    for(int i = 0; i < p; i++){
      memset(used,-1,sizeof(used));
      queue<P> que;
      que.push(P(v[i].x,v[i].y));
      used[v[i].x][v[i].y] = 0;
      while(!que.empty()){
	P a = que.front(); que.pop();
	if(c[a.x][a.y] == -1) continue;
	if(c[a.x][a.y] != '.'){
	  d[i][(int)c[a.x][a.y]] = used[a.x][a.y];
	}
	for(int i = 0; i < 4; i++){
	  int nx = a.x + dx[i];
	  int ny = a.y + dy[i];
	  if(used[nx][ny] == -1){
	    que.push(P(nx,ny));
	    used[nx][ny] = used[a.x][a.y] + 1;
	  }
	}
      }

      for(int j = 0; j < p; j++){
	if(d[i][j] == -1){
	  f = true;
	  break;
	}
      }
      if(f) break;
    }
    if(f){
      cout << -1 << endl;
    }else{
      memset(dp,-1,sizeof(dp));
      cout << solve(1,0) << endl;
    }
  }
}