はやし屋

競技プログラミングのメモ きたない

AOJ 0215: Pachimon Creature

約二年ぶりに解きなおした.懐かしい.
属性ごとの座標を配列に保存して,
dp[今の属性][今の属性から伸びてる辺が何番目のものか] = 最短路;
みたいな感じでやりました.
きれいに書きたい.

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<map>
#include<cstring>
using namespace std;
 
int w , h;
struct Point {int y , x;};
 
vector < Point > el[5];
Point S , G;
int dp[5][1024];
int start_el;
 
void init(){
  for(int i = 0 ; i < 5 ; ++i)el[i].clear();
}
 
int dist(Point a , Point b){
  return abs(a.y-b.y) + abs(a.x-b.x);
}
 
//                      element idx 
int solve(int element , int idx , int fl){
  if(~dp[element][idx])return dp[element][idx];
  if((element+1)%5 == start_el)return dist(el[element][idx],G);
  int ret = 1 << 28 ;
  for(int i = 0 ; i < el[(element+1)%5].size() ; ++i){
    int d = solve((element+1)%5,i,fl|1);
    d += dist(fl ? el[element][idx] : S,el[(element+1)%5][i]);
    ret = min(ret,d);
  }
 
  return dp[element][idx] = ret;
}
 
int main(void){
  while(cin >> w >> h && h){
 
    init();
     
    for(int i = 0 ; i < h ; ++i){
      string s;cin >> s;
      for(int j = 0 ; j < s.size() ; ++j){
	if(isdigit(s[j]))el[s[j]-'1'].push_back((Point){i,j});
	if(s[j] == 'S')S = (Point){i,j};
	if(s[j] == 'G')G = (Point){i,j};
      }
    }
    int ret = 1 << 28 , ret_el = -1;
    for(int i = 0 ; i < 5 ; ++i){
      start_el = i;
      memset(dp,-1,sizeof(dp));
      int r = solve(i,0,0);
      if(r < ret){
	ret = r;
	ret_el = i;
      }
    }

    if(~ret_el)cout << ret_el + 1 << " " << ret << endl;
    else cout << "NA" << endl;

  }
  return 0 ;
}