SRM 526 500 Problem

500 Problem

using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

#define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
#define For(i, a, b) for (int i=(a); i<(b); ++i)
#define D(x) cout << #x " is " << x << endl

class DucksAlignment {
  public:
  int minimumTime(vector <string> grid);


};

int DucksAlignment::minimumTime(vector <string> grid) {
	int n = grid.size();
	int m = grid[0].size();	
	//Count ducks
	int total_ones = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){				
			if (grid[i][j] == 'o'){
				total_ones++;
			}
		}
	}
	int best = 1 << 30;
	//Brute force on rows
	for (int row = 0; row < n; row++){		
		int time_rows = 0;
		vector <int> position (m,0);
		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++){				
				if (grid[i][j] == 'o'){
					time_rows += abs(row - i);
					position[j] = 1;
				}
			}
		}
		int ones = 0;	
		for (int j = 0; j < m; j++){
			if (position[j] == 1){
				ones++;
			}
			if (position[j] == 0){
				time_rows += min(ones, total_ones - ones);
			}
		}
		best = min(best, time_rows);
	}
	
	//Brute force on columns
	for (int col = 0; col < n; col++){		
		int time_cols = 0;
		vector <int> position (n,0);
		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++){				
				if (grid[i][j] == 'o'){
					time_cols += abs(col - j);
					position[i] = 1;
				}
			}
		}
		int ones = 0;	
		for (int i = 0; i < n; i++){
			if (position[i] == 1){
				ones++;
			}
			if (position[i] == 0){
				time_cols += min(ones, total_ones - ones);
			}
		}
		best = min(best, time_cols);
	}
	return best;
  
}