DucksAlignment.cpp

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

typedef long long 		int64;
typedef vector<int> 		vi;
typedef string 			ST;
typedef stringstream 		SS;
typedef vector< vector<int> > 	vvi;
typedef pair<int,int> 		ii;
typedef vector<string> 		vs;
/*
#if __cplusplus > 199711L	// for g++0x, value of __cplusplus must be greater thana 199711L.
	#define tr(i, c)	for(auto i = begin(c); i != end(c); i++)
#else
	#define tr(i, c)	for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#endif
*/
#define endl		("\n")
#define tr(i, c)	for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define PI		M_PI
#define E 		M_E
#define	eps		1e-9

#define	Sf		scanf
#define	Pf		printf

#define forn(i, n)	for(int i = 0, lets_stop_here = (int)n; i <  lets_stop_here; i++)
#define forab(i, a, b)	for(int i = a, lets_stop_here = (int)b; i <= lets_stop_here; i++)
#define rep(i, a, b)	for(int i = a, lets_stop_here = (int)b; i >= lets_stop_here; i--)

#define	all(c)		(c).begin(), (c).end()
#define	CL(a, b)	memset(a, b, sizeof(a))
#define mp		make_pair
#define pb		push_back

#define	present(x, c)	((c).find(x) != (c).end())	//map & set//
#define	cpresent(x, c)	(find( (c).begin(), (c).end(), x) != (c).end())	//vector & list//

#define read(n)		scanf("%d", &n)
#define write(n)	printf("%d ", n)
#define writeln(n)	printf("%d\n", n)

#if (0 or defined ONLINE_JUDGE)
	#define DEBUG
#else 
	#define DEBUG(x)	cout << #x << " = " << x << "\n"
#endif

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

int DucksAlignment::minimumTime (vector <string> grid) 
{
	int ret = 1e9;
	int N = grid.size(), M = grid[0].size();

	tr(it, grid)
		cout << *it << endl;
	cout << endl;

	forn(r, grid.size()) {
		int tmp = 0;
		vi xyz;
		forn(j, grid[0].size()) {
			int idx = -1;
			forn(i, grid.size()) {
				if(grid[i][j] == 'o') {
					idx = i;
					xyz.pb(j);
				}
			}
			if(idx > -1)
				tmp += abs(r-idx);
		}
		int cost = 1e9;
/*
		tr(it, xyz)
			write(*it);
		cout << endl;
*/
		forn(x, M - xyz.size()+1) {
			int tmpCost = 0;
			forn(i, xyz.size())
				tmpCost += abs(x + i - xyz[i]);
			cost = min(tmpCost, cost);
		}

//		DEBUG(cost);
		ret = min(ret, tmp + cost);
//		DEBUG(ret);
	}

	forn(c, grid[0].size()) {
		int tmp = 0;
		vi xyz;
		forn(i, grid.size()) {
			int idx = -1;
			forn(j, grid[0].size()) {
				if(grid[i][j] == 'o') {
					idx = j;
					xyz.pb(i);
				}
			}
			if(idx > -1)
				tmp += abs(c - idx);
		}
		int cost = 1e9;
		int N = grid.size();
		forn(x, N - xyz.size() + 1) {
			int tmpCost = 0;
			forn(i, xyz.size())
				tmpCost += abs(x + i - xyz[i]);
			cost = min(tmpCost, cost);
		}
		ret = min(ret, tmp+cost);
	}

	return ret;
}

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <string> p0, bool hasAnswer, int p1) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << "\"" << p0[i] << "\"";
	}
	cout << "}";
	cout << "]" << endl;
	DucksAlignment *obj;
	int answer;
	obj = new DucksAlignment();
	clock_t startTime = clock();
	answer = obj->minimumTime(p0);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p1 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p1;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	vector <string> p0;
	int p1;
	
	{
	// ----- test 0 -----
	string t0[] = {".o","o."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 1;
	all_right = KawigiEdit_RunTest(0, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	string t0[] = {".o...","..o..","....o"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 3;
	all_right = KawigiEdit_RunTest(1, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	string t0[] = {"o..........","..o........",".......o...","...........","...........","...........","........o..","..........."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 16;
	all_right = KawigiEdit_RunTest(2, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	string t0[] = {".........","....o....","........."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 0;
	all_right = KawigiEdit_RunTest(3, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	string t0[] = {"...o..........................","............................o.",".o............................","............o.................",".................o............","......................o.......","......o.......................","....o.........................","...............o..............",".......................o......","...........................o..",".......o......................"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 99;
	all_right = KawigiEdit_RunTest(4, p0, true, p1) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// Mr. Dengklek has a rectangular farm conveniently divided into a grid of unit squares. At this moment, each unit square contains at most one duck. Moreover, each row and column of the farm also contains at most one duck. You are given a vector <string> grid. The j-th character of the i-th element of grid will be 'o' if there is exactly one duck in square (i, j), i.e., row i column j, or '.' if there is no duck in that square. 
// 
// Today, Mr. Dengklek wants to align the ducks so that the ducks form a contiguous line. More precisely, assume that there are N ducks on the farm. After the alignment, the ducks must either occupy N contiguous squares in some row or N contiguous squares in some column. To accomplish that, he will move the ducks one at a time. To move a duck in square (a, b) to another empty square (c, d), he needs |a-c| + |b-d| seconds, where |x| denotes the absolute value of x. Mr. Dengklek can always move any duck to any empty square he desires - the other ducks are not obstacles.
// 
// Return the minimum time in seconds Mr. Dengklek needs to align the ducks. Note that restrictions imposed on the initial placement of ducks guarantee that a proper alignment is always possible.
// 
// DEFINITION
// Class:DucksAlignment
// Method:minimumTime
// Parameters:vector <string>
// Returns:int
// Method signature:int minimumTime(vector <string> grid)
// 
// 
// CONSTRAINTS
// -grid will contain between 1 and 50 elements, inclusive.
// -Each element of grid will contain between 1 and 50 characters, inclusive.
// -All elements of grid will contain the same number of characters.
// -Each character of grid will be either 'o' or '.'.
// -Each row in grid will contain at most one character 'o'.
// -Each column in grid will contain at most one character 'o'.
// -grid will contain at least one character 'o'.
// 
// 
// EXAMPLES
// 
// 0)
// {".o",
//  "o."}
// 
// Returns: 1
// 
// Move either duck to an adjacent empty square.
// 
// 1)
// {".o...",
//  "..o..",
//  "....o"}
// 
// Returns: 3
// 
// One of the solutions is: move the the duck in the first row one square to the right, and then move the duck in the last row two squares to the left.
// 
// 2)
// {"o..........",
//  "..o........",
//  ".......o...",
//  "...........",
//  "...........",
//  "...........",
//  "........o..",
//  "..........."}
// 
// Returns: 16
// 
// Align all ducks in the second row.
// 
// 3)
// {".........",
//  "....o....",
//  "........."}
// 
// Returns: 0
// 
// 
// 
// 4)
// {"...o..........................",
//  "............................o.",
//  ".o............................",
//  "............o.................",
//  ".................o............",
//  "......................o.......",
//  "......o.......................",
//  "....o.........................",
//  "...............o..............",
//  ".......................o......",
//  "...........................o..",
//  ".......o......................"}
// 
// Returns: 99
// 
// 
// 
// END KAWIGIEDIT TESTING

//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!