AOJ 0215 - Pachimon Creature

問題文 : パチモンクリーチャー

解法 : 最初に選ぶパチクリを決めると, 次に選ぶパチクリが決まっていく. このパチクリ同士の関係を線で結んでいくと, 必然的にグラフになっている.
ゆえに, この問題はグラフの最短経路を求める問題に帰着できる.
ここでは, たどる辺の本数が高々5本であるため, この最短経路を動的計画法で求めている.

コード :

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>

using namespace std;

typedef struct {
	int x, y;
} Point;

vector<Point> mon[5];
int dp[5][1024];

int dist(Point i, Point j)
{
	return (abs(i.x - j.x) + abs(i.y - j.y));
}

int main()
{
	static char str[1024][1024];
	int W, H;
	Point S, G;
	
	while (1){
		scanf("%d %d", &W, &H);
		
		if (W + H == 0){
			break;
		}
		
		for (int i = 0; i < H; i++){
			scanf("%s", str[i]);
		}
		
		for (int i = 0; i < 5; i++){
			mon[i].clear();
		}
		
		for (int i = 0; i < H; i++){
			for (int j = 0; j < W; j++){
				if (str[i][j] == 'S'){
					S.x = j;
					S.y = i;
				}
				if (str[i][j] == 'G'){
					G.x = j;
					G.y = i;
				}
				if (1 <= str[i][j] - '0' && str[i][j] - '0' <= 5){
					Point t;
					t.x = j;
					t.y = i;
					mon[str[i][j] - '0' - 1].push_back(t);
				}
			}
		}
		
		int acre = 1 << 30, adist = 1 << 30;
		for (int i = 0; i < 5; i++){
			for (int j = 0; j < mon[(i + 1) % 5].size(); j++){
				dp[(i + 1) % 5][j] = dist(S, mon[(i + 1) % 5][j]);
			}
			for (int j = i + 2; j < i + 5; j++){
				int t = j % 5;
				int s = (t + 4) % 5;
				for (int k = 0; k < mon[t].size(); k++){
					dp[t][k] = 1 << 30;
				}
				for (int k = 0; k < mon[t].size(); k++){
					for (int l = 0; l < mon[s].size(); l++){
						dp[t][k] = min(dp[t][k], dp[s][l] + dist(mon[s][l], mon[t][k]));
					}
				}
			}
			int a = 1 << 30;
			for (int j = 0; j < mon[(i + 4) % 5].size(); j++){
				a = min(a, dp[(i + 4) % 5][j] + dist(mon[(i + 4) % 5][j], G));
			}
			if (a < adist){
				adist = a;
				acre = i + 1;
			}
		}
		if (acre != 1 << 30){
			printf("%d %d\n", acre, adist);
		}
		else {
			printf("NA\n");
		}
	}
	
	return (0);
}