SRM 526 DucksAlignment (div1 250)

DucksAlignment.cpp

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

using namespace std;

class DucksAlignment {
    public:
   int minimumTime(vector<string> grid) {
	int M=grid.size(), N=grid[0].size();
	//assumen N>M
	if(M>N){
		vector<string> grid1(N, string(M,'-'));
		//transpose
		for(int c=N-1;c>=0;--c)
			for(int r=0;r<M;++r)
				grid1[N-1-c][r] = grid[r][c];
		grid = grid1;
		swap(M,N);
	}

	vector<int> vc;
    int sm=N, lg=0;
	for(int r=0;r<M;++r)
		for(int c=0;c<N;++c)
			if(grid[r][c]=='o')
					vc.push_back(r); //center at which row

	int sz=vc.size();
    sort(vc.begin(), vc.end());//
    int ans=2500;
    //move all duck to column 'tryc'
	for(int tryc=0;tryc<N;++tryc){ 
        int t=0;
        for(int row: vc){ //can be more clean if we save column 
            for(int c=0;c<N;++c) if(grid[row][c]=='o'){
                t += abs(c - tryc);
			}
        }
        //try to align all, 0 ~ M-sz
        for(int y=0; y+sz<=M;++y){
            int columnCost = 0;
            for(int i=0;i<sz;++i){
                columnCost += abs(vc[i]-(y+i));
            }
            ans = min(ans, t+columnCost);    
        }
	}
    return ans;
    }
};