SRM 526 div1 easy:DucksAlignment

問題

TopCoder Statistics - Problem Statement

解法

まず, あつまるべき座標を決定した際にそれぞれのアヒルはどのように動かすのが最適かを考えてみましょう。

各行にはたかだか 1 匹のアヒルしかいないので, ある一列にアヒルを揃える際は, (a, c), (a+1, c), ..., (a+num-1, c) となりますが (num はアヒルの数), この時 (a, c) には予めいる行番号が一番小さいアヒルを対応させて, (a+1, c) には予めいる行番号が次に小さいアヒルを対応させて, ... とやっていけば良いです。

各列にもたかだか 1 匹のアヒルしかいないので, 同じようにやります。

ということで, 集まるべき座標を決め打ちすればコストは簡単に計算できるので, これらを全探索しましょう。

class DucksAlignment {
public:
    int minimumTime(vector <string> grid) {
        vector<pii> P;
        int n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'o') P.emplace_back(i, j);
        }
        int ans = 100000;
        int num = P.size();
        sort(P.begin(), P.end());
        for (int i = 0; i+num <= n; i++) {
            for (int j = 0; j < m; j++) {
                int tmp = 0;
                for (int k = 0; k < num; k++) {
                    tmp += abs(P[k].first-(i+k)) + abs(P[k].second-j);
                }
                ans = min(ans, tmp);
            }
        }
        for (int i = 0; i < num; i++) swap(P[i].first, P[i].second);
        sort(P.begin(), P.end());
        for (int i = 0; i < n; i++) {
            for (int j = 0; j+num <= m; j++) {
                int tmp = 0;
                for (int k = 0; k < num; k++) {
                    tmp += abs(P[k].second-i) + abs(P[k].first-(j+k));
                }
                ans = min(ans, tmp);
            }
        }
        return ans;
    }