AOJ 0215 - Pachimon Creature

問題概要

横x×縦yのマップが与えられ、マップは以下のもので構成される。

• S : スタート位置
• G : ゴール位置
• 1 : 火属性のモンスター
• 2 : 氷属性のモンスター
• 3 : 木属性のモンスター
• 4 : 土属性のモンスター
• 5 : 水属性のモンスター

モンスターを手に入れる条件

1. 火属性のモンスターは氷属性のモンスターを捕まえることができる。
2. 氷属性のモンスターは木属性のモンスターを捕まえることができる。
3. 木属性のモンスターは土属性のモンスターを捕まえることができる。
4. 土属性のモンスターは水属性のモンスターを捕まえることができる。
5. 水属性のモンスターは火属性のモンスターを捕まえることができる。

(ポ○モンの弱点の関係と同じ。 …なのかな。4がちょっとわからん)

プレイヤーはスタート位置から1~5のモンスターのうちどれかを持った状態で移動を開始する。全てのモンスターを手に入れてゴールに到達することが可能なとき、最初に選んだモンスターの属性番号と最小移動数(最小移動数が複数ある場合は最初に選んだモンスターの属性番号がより小さいもの)を出力せよ。なお、そのような条件でゴールに到達できない場合は"NA"を出力する。

制約

• 2 ≤ x ≤ 1000
• 2 ≤ y ≤ 1000
• 0 ≤ 各属性のモンスターの数 ≤ 1000
• 手持ちのモンスターに関わらずどのマスに何度でも移動可能

解法

dpする。
弱点の関係から、1を持っていたら次は2、2を持っていたら次は3・・・のようにモンスターは順番にしか手に入れることができないので次のような状態でできる。
dp[属性番号][その属性番号の何番目のモンスター] := 最小移動数。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 1e9
typedef pair<int,int> pii;
 
struct Point{
  int x,y;
};
 
int cnt[5];
int dp[5][1002];
Point cr[5][1002];
 
int getMD(const Point &p1,const Point &p2){
  return abs(p1.x-p2.x)+abs(p1.y-p2.y);
}
 
int main(){
  int H,W;
  while(cin >> W >> H, W){
    char in;   
    int sx,sy,gx,gy;
    memset(cnt,0,sizeof(cnt));
    for(int i = 0 ; i < H ; i++){
      for(int j = 0 ; j < W ; j++){
        cin >> in;
        if(in == 'S'){
          sx = j; sy = i;
        }else if(in == 'G'){
          gx = j; gy = i;
        }else if(isdigit(in)){
          int n = in-'1';
          cr[n][cnt[n]++] = (Point){j,i};
        }
      }
    }
    for(int i = 0 ; i < 5 ; i++){
      cr[i][cnt[i]++] = (Point){sx,sy};
    }
    int res = INF, num = -1;
    for(int i = 0 ; i < 5 ; i++){
      for(int j = 0 ; j < 5 ; j++){
        for(int k = 0 ; k < cnt[j] ; k++){
          dp[j][k] = INF;
        }
      }
      dp[i][cnt[i]-1] = 0;
      int nj = i, j = (i+1)%5, ej = (i > 0 ? i-1 : 4);
      while(true){
        int m = nj == i ? 0 : 1;
        for(int k = 0 ; k < cnt[nj]-m ; k++){
          if(dp[nj][k] == INF) continue;
          for(int l = 0 ; l < cnt[j]-m ; l++){
            dp[j][l] = min(dp[j][l],dp[nj][k]+getMD(cr[nj][k],cr[j][l]));
          }
        }
        if(j == ej){
          for(int k = 0 ; k < cnt[j] ; k++){
            int d = dp[j][k] + getMD(cr[j][k],(Point){gx,gy});
            if(d < res){
              res = d;
              num = i+1;
            }
          }
          break;
        }
        nj++; nj %= 5;
        j++; j %= 5;
      }
    }
    if(res == INF){
      cout << "NA" << endl;
    }else{
      cout << num << " " << res << endl;
    }
  }
  return 0;
}