Codeforces 83 C. Track

問題

hxwマスのグリッドのそれぞれに、a-zの文字またはS,Tが書かれている。

SからTのマスへのパスを考えたとき、パス上にある文字をつなげた文字列をsとする。
sに現れるアルファベットの数がk個以下で、最小の長さをもつようなsを求めよ。
複数ある場合は辞書順で最小のものを求めよ。

制約条件

h,w≦50
k≦4

方針

使う文字を限定して探索などをするとTLEになる。
A*探索をする。
ゴールまでのコストの見積りは、現在の文字列の長さ+ゴールまでのマンハッタン距離。

見積りコストが同点の場合は文字列で比較してやるようにする。
すると最初にゴールを見つけたものが辞書順最小になる。
50msくらいで通る。

ソースコード

typedef pair<int,pair<pair<string,int>,int> > node;
const int dy[]={-1,0,1,0}, dx[]={0,-1,0,1};
inline int D(int x1,int y1,int x2,int y2){ return abs(x1-x2)+abs(y1-y2); }

int h,w,k;
string in[50];


void run(){
  cin>>h>>w>>k;
  int sy,sx,gy,gx;
  rep(i,h){
    cin>>in[i];
    rep(j,w){
      if(in[i][j]=='S')sy=i, sx=j;
      else if(in[i][j]=='T')gy=i, gx=j;
    }
  }
  set<pi> s;
  priority_queue<node,vector<node>,greater<node> > q;
  q.push(mp(D(sy,sx,gy,gx),mp(mp("",0),sy*w+sx)));
  while(!q.empty()){
    int y=q.top().second.second/w, x=q.top().second.second%w;
    string str=q.top().second.first.first;
    int mask=q.top().second.first.second;
    q.pop();
    if(s.count(mp(mask,y*w+x)))continue;
    s.insert(mp(mask,y*w+x));
    
    rep(d,4){
      int ny=y+dy[d], nx=x+dx[d];
      if(ny<0||nx<0||ny>=h||nx>=w||ny==sy&&nx==sx)continue;
      if(ny==gy&&nx==gx){
        cout<<str<<endl; return;
      }
      string next=str+in[ny][nx];
      int nmask=mask|1<<in[ny][nx]-'a';
      if(__builtin_popcount(nmask)<=k)
        q.push(mp(D(ny,nx,gy,gx)+next.size(),mp(mp(next,nmask),ny*w+nx)));
    }
  }
  cout<<-1<<endl;
}