Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-21

SRM382 div2 (過去問)

01:50

Medium - CollectingRiders

k-ridersはk回連続で動けるナイト. 板状にいくつかのk-ridersが置かれているので, ひとつのセルに複数のk-ridersが乗れるとすると, 最短何手ですべてのk-ridersがひとつのセルに集まるか.

板状のすべてのセルについて, そのセルがk-ridersの集合地点と仮定して何手で集まれるかを調べ, その最小値を返すというアプローチです. 手数のカウントは, そのセルをスタートしたbfsで各セルへの最短距離を求め, あとはk-ridersの置かれているセルとスタート地点との最短距離の総和をとることで求まります. kの処理は, まず1-ridersと仮定して手数を求め, 最後にそれをkで割ればokです.

mediumにしては難しい問題だった気がします.

class CollectingRiders {
public:
  int minimalMoves(vector <string> board) {
    int ret = -1;
    int dirx[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
    int diry[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
    int visited[board.size()][board[0].size()];
    const int INF = 100000;

    for (int i=0; i<board.size(); i++)
      for (int j=0; j<board[0].size(); j++) {
        for (int k=0; k<board.size(); k++)
          for (int l=0; l<board[0].size(); l++)
            visited[k][l] = INF;
        queue <pair <int, int> > q;
        q.push(make_pair(i, j));
        visited[i][j] = 0;

        while (!q.empty()) {
          pair <int, int> cur = q.front();
          q.pop();
          int cur_x = cur.first;
          int cur_y = cur.second;

          for (int k=0; k<8; k++) {
            int next_x = cur_x + dirx[k];
            int next_y = cur_y + diry[k];
            if (0 <= next_x && next_x < board.size() && 0 <= next_y && next_y < board[0].size() && visited[next_x][next_y] == INF) {
              visited[next_x][next_y] = min(visited[next_x][next_y], visited[cur_x][cur_y] + 1);
              q.push(make_pair(next_x, next_y));
            }
          }
        }

        int sum = 0;
        bool valid = true;
        for (int k=0; k<board.size(); k++)
          for (int l=0; l<board[0].size(); l++)
            if (board[k][l] != '.') {
              if (visited[k][l] == INF) {
                valid = false;
                break;
              } else {
                sum += ceil((double)visited[k][l] / (board[k][l] - '0'));
              }
            }

        if (valid && sum >= 0 && (ret == -1 || ret > sum))
          ret = sum;
      }

    return ret;
  }
};