やっと通った!!
問題文から次に手に入れるべきモンスターの属性はひとつに定まることがわかるので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; } }