RUPC (Ritsumeikan University Programming Contest) 2011 Problem D The Legendary Sword

問題

hxwマスのグリッドに、数字で表される珠が置かれている。
スタートのマスはS、ゴールのグリッドはGである。

ゴールの前に全ての種類の珠に最低一度ずつ触れる必要がある。
珠は、1番の珠→2番の珠と、数字の小さい順に触れなければならない。

同じ数字の珠はどれか一つのみ触れればよい。

ゴールするのにかかる、最短の移動距離を求めよ。
移動は、隣接する上下左右のマスにすることができ、グリッドの外へ出ることはできない。

制約条件

h≦100, w≦100

方針

数字がiである珠のj個目（同じ数字の珠を区別するために、左上から適当に1番、2番とつける）を触るのに必要な、最短の移動距離をdp[i][j]とする。
次に触れる珠はi+1番目の珠のどれかなので、

dp[i+1][k] = min(dp[i][j] + （珠i,jから珠i+1,kへの距離）)の漸化式が成り立つ。

この漸化式にしたがって表を更新するようなDPをすればよい。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
string maze[100][101];

int dp[100][100];

int main()
{
	int h,w;
	while(cin>>w>>h,w){
		int sy,sx,gy,gx,maxtama=0;
		rep(i,h)rep(j,w){
			cin>>maze[i][j];
			if(maze[i][j]=="S")sy=i, sx=j;
			if(maze[i][j]=="G")gy=i, gx=j;
			if(isdigit(maze[i][j][0]))maxtama=max(maxtama,atoi(maze[i][j].c_str()));
		}
		vector<vi> tamas(maxtama+2);
		rep(i,h)rep(j,w)if(isdigit(maze[i][j][0])){
			int num=atoi(maze[i][j].c_str());
			tamas[num].pb(i*w+j);
		}
		tamas[0].pb(sy*w+sx);
		tamas[maxtama+1].pb(gy*w+gx);
		
		vector<vi> dp(maxtama+2);
		rep(i,maxtama+2){
			dp[i].resize(tamas[i].size());
			rep(j,dp[i].size())dp[i][j]=inf;
		}
		
		dp[0][0]=0;
		rep(i,maxtama+1)rep(j,dp[i].size())rep(k,dp[i+1].size()){
			dp[i+1][k]=min(dp[i+1][k],dp[i][j]+
				abs(tamas[i][j]/w-tamas[i+1][k]/w)+abs(tamas[i][j]%w-tamas[i+1][k]%w));
		}
		cout<<dp[maxtama+1][0]<<endl;
	}
	
	return 0;
}