naoya_t@topcoder

SRM382 Div1 Easy: CollectingRiders

過去問, 練習 | 03:01 |

問題読み違えてた。これ本番に1時間15分で解けるだろうか。

• ボード上のある位置について
  • 各駒がそこに辿り着くのに必要な手数を数える。不可能な場合もある。
  • 全駒がそこに（何手かで）辿り着ける場合、合計何手か
• という風に全ての位置について計算し、合計の最も少ないのが答え

サンプルケースが全部通れば通る感じ。

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())

vector<set<pair<int,int> > > moves(10);
vector<pair<int,int> > d(8);

class Piece{
 public:
  int x, y, k;
  Piece(int x_, int y_, int k_){x=x_;y=y_;k=k_;}
};

class CollectingRiders {
  int w,h;
  int gx,gy;
  bool bd[10][10], bdt[10][10], bdv[10][10];
  
  int moves_needed(int xp,int yp){
    rep(x,w) rep(y,h) bd[x][y]=bdv[x][y]=false;
    int time=0;
    if(xp==gx && yp==gy) return 0;
    bd[xp][yp]=bdv[xp][yp]=true;
    while (true) {
      int cnt=0;
      rep(x,w) rep(y,h) bdt[x][y]=false;
      rep(x,w) rep(y,h) {
        if (!bd[x][y]) continue;
        rep(i,8){
          int x_=x+d[i].first, y_=y+d[i].second;
          if ((0<=x_ && x_<w) && (0<=y_ && y_<h)) {
            bdt[x_][y_]=true;
            if(!bdv[x_][y_]){ bdv[x_][y_]=true; cnt++; }
          }
        }
      }
      time++;
      if (bdt[gx][gy]) return time;

      rep(x,w) rep(y,h) bd[x][y]=bdt[x][y];
      if (cnt==0) return -1;
    }
  }
    
 public:
  int minimalMoves(vector<string> board) {
    h=sz(board), w=board[0].length();

    d[0].first = 2; d[0].second = 1;
    d[1].first = 1; d[1].second = 2;
    d[2].first = -1; d[2].second = 2;
    d[3].first = -2; d[3].second = 1;
    d[4].first = -2; d[4].second = -1;
    d[5].first = -1; d[5].second = -2;
    d[6].first = 1; d[6].second = -2;
    d[7].first = 2; d[7].second = -1;

    moves[0].insert(make_pair(0,0));
    for (int i=1;i<=9;i++){
      tr(moves[i-1],it){
        int x=it->first,y=it->second;
        rep(j,8){
          int dx=d[j].first, dy=d[j].second;
          moves[i].insert(make_pair(x+dx,y+dy));
        }
      }
    }

    vector<Piece*> pieces;
    rep(y,h) rep(x,w){
      int c = board[y][x]; if (c!='.') pieces.pb(new Piece(x,y,c-'0'));
    }
    int np=sz(pieces);
    if (np==1) return 0;

    int total_min=INT_MAX;
    for(gx=0;gx<w;gx++) {
      for(gy=0;gy<h;gy++) {
        int total=0;
        rep(i,np){
          Piece* p = pieces[i];
          int mn = moves_needed(p->x,p->y), mn_min;
          if (mn < 0) goto next_xy;
          mn_min = mn/p->k;
          if (mn%p->k > 0) mn_min++;
          total += mn_min;
        }
        if(total<total_min) total_min=total;
     next_xy:
        ;
      }
    }

    tr(pieces,p) delete *p;

    return (total_min==INT_MAX) ? -1 : total_min;
  }
};