1140 Cleaning Robot

AOJ

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1140&lang=jp

ほうしん

幅優先探索で、各汚れたタイルと初期位置との距離を全て求めておきTSPにして解く。

ソース

#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

char mp[20][20];
int dist[20][20];
bool seen[20][20];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
const int inf = 1<<29;

int tsp(int start,vector< vector<int> > G) {
  const int n = G.size(), N = 1<<n;
  int i,j,ret = inf;
  vector< vector<int> > X(n, vector<int>(N, inf));
  vector< vector<int> > Y(n, vector<int>(N, -1));
  rep(i,n) {
    X[i][1<<i] = G[start][i];
    Y[i][1<<i] = start;
  }

  for(int S = 1; S < N; ++S) {
    rep(i,n) {
      if(!(S & (1<<i))) continue;
      rep(j,n) {
	if(S & (1<<j)) continue;
	if(X[j][S|(1<<j)] > X[i][S]+G[i][j]) {
	  X[j][S|(1<<j)] = X[i][S]+G[i][j];
	  Y[j][S|(1<<j)] = i;
	}
      }
    }
  }

  if(X[start].back() >= inf) return -1;
  rep(i,n) ret = min(X[i].back(), mm);
  return mm;
}

int main() {
  int w,h,i,j,k,l,objnum;
  string s;
  while(cin>>w>>h, w|h) {
    objnum = 1;
    rep(i,h) {
      cin>>s;
      rep(j,w) {
	mp[i][j] = s[j];
	if(s[j] == 'o') mp[i][j] = 0;
	if(s[j] == '*') mp[i][j] = objnum++;
      }
    }

    vector<vector<int> > G(objnum, vector<int>(objnum, inf));
    rep(i,objnum) G[i][i] = 0;
    rep(i,objnum) {
      int sx,sy;
      rep(j,h) rep(k,w) if(mp[j][k] == i) sx = k, sy = j;
      memset(dist, -1, sizeof(dist));
      memset(seen, false, sizeof(seen));
      queue<pair<int,int> > Q;
      Q.push(make_pair(sy,sx));
      seen[sy][sx] = true;
      dist[sy][sx] = 0;
      while(!Q.empty()) {
	int x = Q.front().second,y = Q.front().first; Q.pop();
	rep(l,4) {
	  int nx = x+dx[l],ny = y+dy[l];
	  if(nx < 0 || nx >= w || ny < 0 || ny >= h || seen[ny][nx]) continue;
	  if(mp[ny][nx] == 'x') continue;
          if(dist[ny][nx] == -1) dist[ny][nx] = dist[y][x]+1;
	  else dist[ny][nx] = min(dist[ny][nx],dist[y][x]+1);
	  seen[ny][nx] = true;
	  Q.push(make_pair(ny,nx));
	}
      }

      rep(j,h) rep(k,w) {
	if(0 <= mp[j][k] && mp[j][k] <= objnum) {
	  if(dist[j][k] == -1) continue;
	  G[mp[j][k]][i] = G[i][mp[j][k]] = dist[j][k];
	}
      }
    }

      long long ans = tsp(0,G);
      if(ans >= inf) cout<<-1<<endl;
      else cout<<ans<<endl;
  }
}