ぱーぽーの競プロ記

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

AOJ 0215 Pachimon Creature

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

若干ポ○モンみたいな雰囲気があります。
5種類のモンスターを仲間にしてラスボスを倒しにいこう、その最短過程(最小移動数)を求めよ的な問題です。


・解法
動的計画法(DP)で解くことができます。
(※BFSではおそらく解くことができません。最初はアホみたいにずっとBFSでやってましたが、どうしてもMLEが解消できずに諦めてしまいました。想定解法と全く違うことしててとても悔しかったです。結果的に他のブログを参考にしながら解くことにしました。)

方針としては、最初仲間にする(おじさんから貰う)モンスターを決めてそこからDPをするみたいな感じです。5種類のモンスターがいるので、合計5回DPをすることになります。

この5種類のモンスター(火・氷・木・土・水属性)をそれぞれ仲間にするには条件があります。
例えば氷属性のモンスターを仲間にしたいなら火属性のモンスターを仲間にしていないといけない。 水属性のモンスターを仲間にしたいなら土属性のモンスターを仲間にしていないといけない。 ...みたいな感じです。
要するに最初仲間にするモンスターが決まれば、残り4種類のモンスターをどの順番で仲間にしに行くかというのが定まるということです。


ソースコード

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

#define f first
#define s second
typedef pair<int,int> P;

static const int INF = (1 << 29);

int h,w;
int minCost[5][1000];
char c;
P start,goal;
vector<P> p[5];

int dist(P p1, P p2){
   return abs(p1.f - p2.f) + abs(p1.s - p2.s);
}

P solve(){
   P ans = P(INF,INF);
	
   for(int S = 0 ; S < 5 ; S++){
      for(int i = 0 ; i < 5 ; i++){
         for(int j = 0 ; j < 1000 ; j++){
            minCost[i][j] = INF;
         }
      }
      
      for(int j = 0 ; j < p[(S+1)%5].size() ; j++){
         minCost[(S+1)%5][j] = dist(start, p[(S+1)%5][j]);
      }

      for(int i = S+1 ; i < S+4 ; i++){
         for(int j = 0 ; j < p[i%5].size() ; j++){
            for(int k = 0 ; k < p[(i+1)%5].size() ; k++)
               minCost[(i+1)%5][k] = min(minCost[(i+1)%5][k], minCost[i%5][j]+dist(p[i%5][j], p[(i+1)%5][k]));
         }
      }
		
      int cost = INF;
      for(int i = 0 ; i < p[(S+4)%5].size() ; i++){
         cost = min(cost, minCost[(S+4)%5][i]+dist(p[(S+4)%5][i], goal));
      }

      if(ans.s > cost){
         ans = P(S+1, cost);
      }
   }
   return ans;
}

int main(){
   while(cin >> w >> h, (w|h)){
      for(int i = 0 ; i < 5 ; i++){
         p[i].clear();
      }
      
      for(int i = 0 ; i < h ; i++){
         for(int j = 0 ; j < w ; j++){
            cin >> c;
            if(c=='.');
            else if(c=='S'){
               start = P(i,j);
            }
            else if(c=='G'){
               goal = P(i,j);
            }
            else{
               p[(int)(c - '0') - 1].push_back(P(i,j));
            }
         }
      }
      
      P ans = solve();
      if(ans.f==INF && ans.s==INF)puts("NA");
      else cout << ans.f << " " << ans.s << endl;
   }
   return 0;
}