SRM526 Div1 Easy(250), Div2 Medium(500) DucksAlignment

TopCoder

DucksAlignment

カモの並べ方について全探索。カモのxとy座標をそれぞれソートしておけば、順番に並べるのが最適。問題の１列にカモは高々１匹という制約から、カモの移動中に他のカモが邪魔になることはない。

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class DucksAlignment{public:
int minimumTime( vector <string> grid )
{
    int h = (int)grid.size();
    int w = (int)grid[0].size();
    vector<int> dx, dy;
    for ( int y=0; y<h; y++ )
    for ( int x=0; x<w; x++ )
        if ( grid[y][x]=='o' )
            dx.push_back(x),
            dy.push_back(y);
    sort(dx.begin(),dx.end());
    sort(dy.begin(),dy.end());
    int N = (int)dx.size();

    int ans = 9999;
    //  横
    for ( int y=0; y<h; y++ )
    for ( int x=0; x+N<=w; x++ )
    {
        int t = 0;
        for ( int i=0; i<N; i++ )
            t += abs(x+i-dx[i])+abs(y-dy[i]);
        ans = min( ans, t );
    }
    //  縦
    for ( int y=0; y+N<=h; y++ )
    for ( int x=0; x<w; x++ )
    {
        int t = 0;
        for ( int i=0; i<N; i++ )
            t += abs(x-dx[i])+abs(y+i-dy[i]);
        ans = min( ans, t );
    }
    return ans;
}};