Pの競プロ記

競技プログラミングに関することを書きます。

AOJ 2419 Acrophobia

概要


問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2419

フィールドに散らばっている巻物を全て集めてゴールに行くまでにかかる最短距離を求める問題です。


解法


幅優先探索(BFS)で解くことができます。

この問題は探索する前までの前処理が面倒だと思います。
まず巻物がどこに置いてあるか、そしてそれぞれの巻物を区別するために別の配列を用意し、ビットで管理します。
あとフィールドに穴があると移動にかかるコストが変わるのでその計算も先にやっておきます。
以下のような感じで求めることができます。

rep(i,h){
  rep(j,w){
    if(G[i][j]=='#'){
      int x = i;
      int y = j;
      for(int nx = x - 3 ; nx <= x + 3 ; nx++){
        for(int ny = y - 3 ; ny <= y + 3 ; ny++){
          if(0<=nx&&nx<h && 0<=ny&&ny<w){
            cost[nx][ny] = max(cost[nx][ny], 4 - max(abs(x-nx),abs(y-ny)));
          }
        }
      }
    }
  }
}

あとはキューに現在地・現在のコスト・巻物の情報をビットで持たせ、探索していきます。


ソースコード

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
 
#define rep(i,n) for(int i = 0; i < (int)(n); i++)

#define f first
#define s second
#define mp make_pair
 
static const int dx[] = {1,-1,0,0};
static const int dy[] = {0,0,1,-1};
static const int INF = (1 << 29);
 
typedef long long ll;
 
struct State{
  int x,y,cost,collect;
  State(){}
  State(int x, int y, int c, int col):x(x),y(y),cost(c),collect(col){}
 
  bool operator < (State s) const{
    return cost > s.cost;
  }
};
 
int w,h;
int sx,sy;
int cnt;
int cost[100][100];
int makimono[100][100];
int minCost[100][100][(1 << 5)];
char G[100][100];
 
void init(){
  rep(i,h) rep(j,w) cost[i][j] = 1;
  rep(i,h){
    rep(j,w){
      if(G[i][j]=='#'){
        int x = i;
        int y = j;
        for(int nx = x - 3 ; nx <= x + 3 ; nx++){
          for(int ny = y - 3 ; ny <= y + 3 ; ny++){
            if(0<=nx&&nx<h && 0<=ny&&ny<w){
              cost[nx][ny] = max(cost[nx][ny], 4 - max(abs(x-nx),abs(y-ny)));
            }
          }
        }
      }
    }
  }
  rep(i,h) rep(j,w) rep(k,(1 << cnt)) minCost[i][j][k] = INF;
}
 
int solve(){
  init();
  priority_queue<State> pq;
  pq.push(State(sx,sy,0,0));
  
  while(!pq.empty()){
    State p = pq.top();
    pq.pop();
 
    if(G[p.x][p.y] == 'G' && p.collect == (1 << cnt) - 1) return p.cost;
    
    if(minCost[p.x][p.y][p.collect] <= p.cost) continue;
    minCost[p.x][p.y][p.collect] = p.cost;
    
    rep(k,4){
      int nx = p.x + dx[k];
      int ny = p.y + dy[k];
      if(0<=nx&&nx<h && 0<=ny&&ny<w && G[nx][ny]!='#'){
        int tmpCost = p.cost + cost[p.x][p.y];
        int tmpCollect = p.collect | makimono[nx][ny];
        if(minCost[nx][ny][tmpCollect] > tmpCost){
          pq.push(State(nx,ny,tmpCost,tmpCollect));
        }
      }
    }
  }
  return -1;
}
 
int main(){
  cin >> w >> h;
  rep(i,h){
    rep(j,w){
      cin >> G[i][j];
      if(G[i][j]=='M'){
        makimono[i][j] |= (1 << cnt);
        cnt++;
      }
      if(G[i][j]=='S'){
        sx = i;
        sy = j;
      }
    }
  }
  cout << solve() << endl;
  return 0;
}