AOJ0215 パチモンクリーチャー

解法

動的計画法じゃないかな?グラフにしたら勝った。
バグ死してた。

ソース

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
using namespace std;
#define INF ( 1 << 30 )
#define fr first
#define sc second
typedef pair < int , int > Pi;
typedef pair < Pi , Pi > Pii;
const int dy[] = { 0, 1, -1, 0}, dx[] = { 1, 0, 0, -1};
int h, w, Sx, Sy, Gx, Gy;
vector< Pi > hoge[5];
int dp[5][1000], num;
char c;
int dis(Pi x1,Pi x2){
  return abs(x1.fr - x2.fr) + abs(x1.sc - x2.sc);
}
int rec(int now,int java){
  if(dp[now][java]) return dp[now][java];
  int ret = INF, next = ( now + 1 ) % 5;
  if(now == num) ret = dis(hoge[now][java],Pi(Gy,Gx));
  else for(int i = 0 ; i < hoge[next].size() ; i++ ){
    ret = min( ret, rec( next, i) + dis(hoge[now][java],hoge[next][i]));
  }
  return dp[now][java] = ret;
}
int main(){
  while(cin >> w >> h , w){
    for(int i = 0 ; i < 5 ; i++ ) hoge[i].clear();
    for(int i = 0 ; i < h ; i++ ){
      for(int j = 0 ; j < w ; j++ ){
        cin >> c;
        if(c == 'S') Sy = i, Sx = j;
        else if(c == 'G') Gy = i, Gx = j;
        else if(c != '.') hoge[c-'1'].push_back(Pi(i,j));
      }
    }
    Pi ret = Pi(INF,INF);
    for(int i = 0 ; i < 5 ; i++ ){
        for(int j = 0 ; j < 5 ; j++ )
          for(int k = 0 ; k < 1000 ; k++ ) dp[j][k] = 0;
      num = ( i + 4 ) % 5;
      int next = ( i + 1 ) % 5, tmp = INF;
      for(int j = 0 ; j < hoge[next].size() ; j++ ){
        ret = min( ret, Pi(rec( next, j) + dis(Pi(Sy,Sx),hoge[next][j]), i+1));
      }
    }
    if( ret.fr == INF ) cout << "NA" << endl;
    else cout << ret.sc << " " << ret.fr << endl;
  }
}