読者です 読者をやめる 読者になる 読者になる

AOJ Problem 1140 : Cleaning Robot

AOJ

問題文:404 Not Found

幅優先探索 + 巡回セールスマンな問題。

先に汚れ同士の最短経路を計算しておけば10!解法でも通るかもしれない。

巡回セールスマンの実装の軽さは異常。

#include <iostream>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (1<<21)
static const int dx[]={1,-1,0,0} , dy[]={0,0,-1,1};
char data[30][30];

struct P{
	int x,y;
	P(int a,int b){x=a,y=b;}
	bool operator ==(const P& a){ return x == a.x && y == a.y; }
};

int bfs(P s,P g){
	// 確定ノード初期化 , 未訪問ならば-1、そうでなければsからの最短距離
	int done[30][30];
	rep(i,30)rep(j,30)done[i][j] = -1;
	
	queue<P>Q;
	Q.push(s);
	done[s.y][s.x] = 0;
	
	while(!Q.empty()){
		P q = Q.front(); Q.pop();
		
		if(q == g) return done[g.y][g.x];
		
		rep(i,4){
			P t = P(q.x+dx[i],q.y+dy[i]);
			if(data[t.y][t.x] == 'x' || ~done[t.y][t.x]){
				continue;
			}else{
				done[t.y][t.x] = done[q.y][q.x]+1;
				Q.push(t);
			}
		}
	}
	return INF;
}
int main(){
	int W,H;
	while(cin >> W >> H , W){
		// マップ初期化
		rep(i,30)rep(j,30)data[i][j] = 'x';
		
		// 入力
		rep(i,H)rep(j,W)
			cin >> data[i+1][j+1];
		
		// ロボット・汚れタイルの位置・個数取得
		P s(0,0);
		vector<P> pos;
		rep(i,30)rep(j,30)
			if(data[i][j] == '*') pos.push_back(P(j,i));
			else if(data[i][j] == 'o')s = P(j,i);
		int n = pos.size();

		// 各汚れタイル同士の最短経路を計算しておく。
		int dist[10][10] = {0};
		rep(i,n)rep(j,n)dist[i][j] = bfs(pos[i],pos[j]);

		// 巡回セールスマン初期化
		int dp[1<<10][10];
		rep(i,1<<10)rep(j,10)dp[i][j] = INF;
		
		// 巡回セールスマン
		rep(i,n) dp[1<<i][i] = bfs(s,pos[i]);
		rep(i,1<<n)rep(j,n)rep(k,n)
			dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k],dp[i][j]+dist[j][k]);
		
		// 出力
		int ans = INF;
		rep(i,n)ans = min(ans,dp[(1<<n)-1][i]);
		cout << (ans<INF?ans:-1) << endl;
	}
}