問題文: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; } }