SRM526 Div1 Easy

250
集める場所を決めて、端から順に移動させる。

bool cmp(pair<int, int> a, pair<int, int> b)
{
  return a.second < b.second;
}

class DucksAlignment {
public:
  int minimumTime(vector <string> g)
  {
    int ret = 1 << 30;

    vector< pair<int, int> > v;
    for (int i = 0; i < (int)g.size(); ++i) {
      for (int j = 0; j < (int)g[i].size(); ++j) {
        if (g[i][j] == 'o') {
          v.push_back(make_pair(i, j));
        }
      }
    }
    sort(v.begin(), v.end(), cmp);

    for (int i = 0; i < (int)g.size(); ++i) {
      for (int j = 0; j + (int)v.size() <= (int)g[i].size(); ++j) {
        int sum = 0;
        for (int k = 0; k < (int)v.size(); ++k) {
          sum += abs(v[k].first - i) + abs(v[k].second - (j + k));
        }
        ret = min(ret, sum);
      }
    }

    return ret;
  }
};