読者です 読者をやめる 読者になる 読者になる

AOJ Problem 0215 : Pachimon Creature

404 Not Found

やっと通った!!

問題文から次に手に入れるべきモンスターの属性はひとつに定まることがわかるのでDAGのDP?る。

最初自分が書いたコードでは、"S2345G"みたいなマップが与えられた時にNAを返していた。("1 5")が正しい。DPの初期化は気をつけなければならない。

ホントこれで3~4時間使ったぞ・・・・。変数名が謎なのはご愛嬌。

#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
struct P{int x,y,cost;};
#define INF (1<<25)
#define rep(i,n) for(int i=0; i<n ;i++)

int dist(P a,P b){
	return abs(a.x-b.x) + abs(a.y-b.y);
}
int main(){
	int w,h;
	
	while(cin >> w >> h , w) {
		vector<P> data[5];
		P start , goal ;
		
		start.cost = 0 , goal.cost = 0;
		
		rep(i,h)rep(j,w){
			char c;	cin >> c;
			if(c != '.'){
				if(c == 'S')start.x = j , start.y = i;	
				else if(c == 'G')goal.x = j , goal.y = i;
				else P t = {j,i,0} , data[c-'1'].push_back(t);
			}
		}
		int ret = INF , num ;
		
		P dp[5][1000];
		
		rep(lp,5){ // start
			rep(i,5)rep(j,1000){dp[i][j].cost = INF;}
			
			int so = (lp+1)%5;
			rep(i,data[so].size()){
				dp[so][i] = data[so][i];
				dp[so][i].cost = dist(data[so][i],start);
			}
			
			rep(Z,3){ // remain 
				int z = (lp+Z+2)%5;
				int prev = (z+4)%5;
				rep(i,data[prev].size()){ // prev
					rep(j,data[z].size()){ //cur
						int cost = dp[prev][i].cost + dist(dp[prev][i],data[z][j]);
						if(dp[z][j].cost > cost){
							dp[z][j] = data[z][j] , dp[z][j].cost = cost;
						}
					}
				}
			}
			rep(i,data[(lp+4)%5].size() ){
				int kCost = dp[(lp+4)%5][i].cost + dist(dp[(lp+4)%5][i],goal);
				if( kCost < ret){
					ret = kCost , num = lp+1; 
				}
			}
		}
		
		if(ret == INF)cout << "NA" << endl; 
		else cout << num << " " << ret << endl; 
	}
}