TopCoder SRM 382 Div1 Easy CollectingRiders

問題

チェスの駒でriderというものを考える。
一回の移動で、k-riderはk回以下のナイトの移動がまとめてできる。

チェス盤のboard[i][j]が数字kのとき、
(i,j)のマスにはk-riderがいる。'.'のときは何もない。

全てのriderを一つのマスに集めるために必要な手数の最小値を求めよ。
同じマスに複数の駒があってもよいものとする。

制約条件

boardの行≦10
boardの列≦10
board[i][j]は'0'-'9'または'.'

方針

集めるマスを全通り試して、全部集める。
あらかじめ全マス間のナイトでの移動回数をワーシャルフロイドで求めておくと書きやすい。

ソースコード

const int dy[]={-1,-2,-2,-1,1,2,2,1},dx[]={-2,-1,1,2,2,1,-1,-2};
int d[100][100];

class CollectingRiders {
  public:
  int minimalMoves(vector <string> board) {
    int h=board.size(),w=board[0].size();
    rep(i,h*w)rep(j,h*w)d[i][j]=i==j?0:inf;
    rep(i,h)rep(j,w)rep(k,8){
      int y=i+dy[k],x=j+dx[k];
      if(y<0||x<0||y>=h||x>=w)continue;
      d[i*w+j][y*w+x]=1;
    }
    rep(k,h*w)rep(i,h*w)rep(j,h*w)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
      
    int ans=inf;
    rep(g,h*w){
      int tmp=0;
      rep(i,h*w)if(isdigit(board[i/w][i%w])){
        int k=board[i/w][i%w]-'0';
        if(d[g][i]==inf)tmp=inf;
        else tmp+=(d[g][i]+k-1)/k;
      }
      ans=min(ans,tmp);
    }
    return ans>=inf?-1:ans;
  }
};