AOJ 0215 - Pachimon Creature

bitDPかな(違う)
あれ出力とちがうかも(違わない)
あ，通った

を属性がiのパチモンがいる場所の集合とする．
(ただし，始点，終点をそれぞれとしパチモンと見る．)
お供のパチモンの属性を選ぶ(とする)
はを捕まえられる属性，はを...とする．
の最短路を求める．
このとき，メモ化を用いるといいです．
C_0の選び方は5通り，全てに対して調べ最小の値を得る．
頑張って図にしてみました．

#include<iostream>
#include<vector>
#include<algorithm>

struct P{
    int x, y;
};
 
std::vector<P> creature[7];//0は始点, 6は終点となっている
const int INF = 1 << 24;
//dp[ゲットしたパチモンの匹数][さっきつかまえた種族][さっきつかまえたパチモンの番号]: 最小手数
int dp[5][5][1000];
 
int rec(int i, int t, int n){
	if(dp[i][t][n] >= 0){
		return dp[i][t][n];
	}
 
	if(i == 4){
		int x_diff = abs(creature[6][0].x - creature[t][n].x),
			y_diff = abs(creature[6][0].y - creature[t][n].y);
		return x_diff + y_diff;
	}

	//t+1へ行こう
	int res = INF, prev_res;
	for(int v=0;v<creature[t+1].size();v++){
		int x_diff = abs(creature[t+1][v].x - creature[t][n].x),
			y_diff = abs(creature[t+1][v].y - creature[t][n].y);
		res = std::min(res, rec(i+1, t+1, v) + x_diff + y_diff);
	}

	return dp[i][t][n] = res;
}
 
int main(){
	int w, h;
	while(std::cin >> w >> h, w){
		for(int i=0;i<7;i++)creature[i].clear();
 
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				char c;
				std::cin >> c;
				if(c == 'S'){
					creature[0].push_back({j, i});
				}else if(c == 'G'){
					creature[6].push_back({j, i});
				}else if('1' <= c && c <= '5'){
					creature[c-'0'].push_back({j, i});
				}
			}
		}
 
		int res = INF, type;
		for(int i=1;i<=5;i++){
			for(int S=0;S<5;S++){
				for(int t=0;t<5;t++){
					for(int n=0;n<1000;n++){
						dp[S][t][n] = -1;
					}
				}
			}

			std::rotate(creature+1, creature+2, creature+6);

			if(rec(0, 0, 0) < res){
				res = rec(0, 0, 0);
				type = i;
			}
		}
 
		if(res == INF){
			std::cout << "NA" << std::endl;
		}else{
			std::cout << type << " " << res << std::endl;
		}
	}
}