パチモンクリーチャー

パソコン甲子園2009 問題11 パチモンクリーチャー

問題文

X×Y個のセルから成るグリッド上のスタート地点から出発し、全５種類のパチクリ（生物）を捕まえた状態でゴール地点まで行く最短コストを求める問題です。各パチクリはそれぞれ、火、氷、木、土、水の属性を持ち、火のパチクリは氷のパチクリを捕まえることができ、氷のパチクリは木のパチクリを捕まえることができ、といったように火→氷→木→土→水→火というような属性の関連があります。スタート地点で最初に持つパチクリを１つ選ぶことができます。グリッドのサイズx, y はそれぞれ2以上1000以下で、各属性のパチクリの数はそれぞれ0以上1000以下です（全体の数は5000以下）。

最初に１つのパチクリを選んだ後のパチクリを捕まえる順番は、上記属性の関連の順番になります。例えば最初に火の属性をもつパチクリを持っていれば、氷、木、土、水の属性をもつパチクリを順番に捕まえてゴールに行けばよいので、下図に示すDAG（Directed Acyclic Graph）の最短コストを求めることになります。下図は、3体の氷のパチクリ、2体の木のパチクリ、3体の土のパチクリ、2体の水のパチクリを含むグリッドをDAGで表したものです。捕まえられないパチクリがいるマスを通っても現在保持しているパチクリの状態に影響はないので、ノード間の距離は対応するマス間のマンハッタン距離（x座標の差とy座標の差の和）となります。スタート地点で選ぶパチクリを変えて（５種類分ありますが、下図では最初に火のパチクリを選んでいます）、動的計画法によってゴールまでの最短コストを求めます。

#include<cstdio>
#include<iostream>
using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++ )
#define MAX 1000
#define INFTY (1<<21)
struct Point{ int x, y; };
int H, W, sy, sx, gy, gx, cnt[5];
Point P[5][MAX];
int D[5][MAX];

inline int mdist(int x1, int y1, int x2, int y2){
    return max(x1, x2) - min(x1, x2) + max(y1, y2) - min(y1, y2);
}

void compute(){
    int opts, optc = INFTY;
    int t;
    rep(s, 5){
        rep(i, 5) rep(j, cnt[i]) D[i][j] = INFTY;
        t = (s+1)%5;
        rep(j, cnt[t]) D[t][j] = mdist(sx, sy, P[t][j].x, P[t][j].y );
        for ( int i = s+1; i < s + 5; i++ ){
            int b = (i)%5;
            int e = (i+1)%5;
            rep(k, cnt[b]) rep(l, cnt[e]) {
                D[e][l] = min(D[e][l], D[b][k] + mdist(P[b][k].x, P[b][k].y, P[e][l].x, P[e][l].y));
            }
        }
	t = (s+4)%5;
        rep(j, cnt[t] ){
            if ( D[t][j] + mdist(gx, gy, P[t][j].x, P[t][j].y ) < optc ){
                optc = D[t][j] + mdist(gx, gy, P[t][j].x, P[t][j].y);
                opts = s;
            }
        }
    }
    if ( optc == INFTY ) cout << "NA" << endl;
    else cout << opts+1 << " " << optc << endl;
}

main(){
    char ch;
    while(cin >> W >> H && W){
        rep(i, 5) cnt[i] = 0;
        rep(y, H) rep(x, W) {
	    cin >> ch;
	    if ( ch == '.' ) continue;
	    if ( ch == 'S' ){
		sy = y; sx = x;
	    } else if ( ch == 'G' ){
		gy = y; gx = x;
	    } else {
		int p = ch -'0' - 1;
		P[p][cnt[p]].x = x;
		P[p][cnt[p]++].y = y;
	    }
        }
        compute();
    }
}