DropCoins.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <climits>
#include <cstring>
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;

#define Pf	printf
#define	Sf	scanf

#define	ep	1e-9
#define PI M_PI
#define E M_E

#define	CL(a, b)	memset(a, b, sizeof(a))
#define	mp	make_pair

#define	pb	push_back

#define	all(c)	(c).begin(), (c).end()
#define	tr(i, c)	for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

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

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

struct Node {
	int step, cnt;
	vs v;
	Node(vs a, int _step = 0) {
		v = a;
		step = _step;
		cnt = 0;
		forn(i, v.size())	forn(j, v[i].size())
			cnt += v[i][j] == 'o';
	}
};

ST str;

bool operator < (const Node & a, const Node &b) {
	return a.v < b.v;
}

vs moveup(vs a) {
	vs ret ;
	forab(i, 1, a.size() -1)
		ret.pb(a[i]);
	ret.pb(str);

	return ret;
}

vs movedown(vs a) {
	vs ret ;
	ret.pb(str);
	forn(i, a.size() -1)
		ret.pb(a[i]);

	return ret;
}

vs moveleft(vs a) {
	vs ret;
	ret.clear();

	ret = a;
	forn(i, ret.size()) {
		ret[i] = ret[i].substr(1);
		ret[i] += '.';
	}
	return ret;
}

vs moveright(vs a) {
	vs ret;
	ret = a;
	int sz = ret[0].size();

	forn(i, ret.size()) {
		ret[i] = "." + ret[i].substr(0, sz-1);
	}
	return ret;
}

class DropCoins
{
public:
	int getMinimum(vector <string> b, int K)
	{
		str = "";
		forn(i, b[0].length())	str+= ".";

		set <vs> s;
		queue <Node> q;
		s.insert(b);
		q.push(Node(b, 0));
//		cout << Node(b, 0).cnt << endl;
//		Pf("(%d x %d)\n", b.size(), b[0].size());

		while(!q.empty()) {
			Node n = q.front();	q.pop();
			if(n.cnt == K)	return n.step;

			vs  vl = moveleft(n.v);
			Node nl (vl, n.step+1);
			if(nl.cnt == K)	return nl.step;
			if(nl.cnt >= K && s.find(vl) == s.end()) {
				s.insert(vl);
				q.push(nl);
			}

			vs  vr = moveright(n.v);
			Node nr (vr, n.step+1);
			if(nr.cnt == K)	return nr.step;
			if(nr.cnt >= K && s.find(vr) == s.end()) {
				s.insert(vr);
				q.push(nr);
			}


			vs  vt = moveup(n.v);
			Node nt (vt, n.step+1);
			if(nt.cnt == K)	return nt.step;
			if(nt.cnt >= K && s.find(vt) == s.end()) {
				s.insert(vt);
				q.push(nt);
			}

			vs  vb = movedown(n.v);
			Node nb (vb, n.step+1);
			if(nb.cnt == K)	return nb.step;
			if(nb.cnt >= K && s.find(vb) == s.end()) {
				s.insert(vb);
				q.push(nb);
			}


		}

		return -1;
	}
};

// 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, int p1, bool hasAnswer, int p2) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << "\"" << p0[i] << "\"";
	}
	cout << "}" << "," << p1;
	cout << "]" << endl;
	DropCoins *obj;
	int answer;
	obj = new DropCoins();
	clock_t startTime = clock();
	answer = obj->getMinimum(p0, p1);
	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" << p2 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p2;
	}
	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;
	int p2;
	
	{
	// ----- test 0 -----
	string t0[] = {".o..","oooo","..o."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 3;
	p2 = 2;
	all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	string t0[] = {".....o","......","oooooo","oooooo","......","o....."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 12;
	p2 = 3;
	all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	string t0[] = {"....",".oo.",".oo.","...."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 3;
	p2 = -1;
	all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	string t0[] = {".......","..ooo..","ooooooo",".oo.oo.","oo...oo"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 12;
	p2 = 4;
	all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	string t0[] = {".................",".ooooooo...oooo..",".ooooooo..oooooo.",".oo.......oo..oo.",".oo.......oo..oo.",".ooooo.....oooo..",".ooooooo...oooo..",".....ooo..oo..oo.","......oo..oo..oo.",".ooooooo..oooooo.",".oooooo....oooo..","................."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 58;
	p2 = 6;
	all_right = KawigiEdit_RunTest(4, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	string t0[] = {"oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooo"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 1;
	p2 = -1;
	all_right = KawigiEdit_RunTest(5, p0, p1, true, p2) && 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
// There is a rectangle divided into 1x1 cells. Each cell is either empty or it contains a single coin. 
// 
// You can apply the following operation repeatedly.
// 
// First, choose one of the directions: up, down, left, or right. 
// Then, move all coins in the chosen direction by exactly 1 cell. If this would cause a coin to move out of the rectangle, the coin drops out from the rectangle and disappears. 
// 
// Your objective in this problem is to apply the operations so that the number of coins remaining on the rectangle becomes exactly K.
// 
// You are given the int K and a vector <string> board that describes the initial state of the rectangle. More precisely, character j of element i of board is 'o' if i-th row of j-th column of the rectangle contains a coin, and it is '.' otherwise.
// 
// Return the minimum number of operations you have to perform. If the objective is impossible, return -1.
// 
// DEFINITION
// Class:DropCoins
// Method:getMinimum
// Parameters:vector <string>, int
// Returns:int
// Method signature:int getMinimum(vector <string> board, int K)
// 
// 
// CONSTRAINTS
// -board will contain between 1 and 30 elements, inclusive.
// -Each element of board will contain between 1 and 30 characters, inclusive.
// -All elements of board will contain the same number of characters.
// -Each character in each element of board will be either '.' or 'o'.
// -K will be between 1 and 900, inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// {".o.."
// ,"oooo"
// ,"..o."}
// 
// 3
// 
// Returns: 2
// 
// One of the optimal solutions is to move coins to the right twice.
// 
// 1)
// {".....o"
// ,"......"
// ,"oooooo"
// ,"oooooo"
// ,"......"
// ,"o....."}
// 
// 12
// 
// Returns: 3
// 
// One of the optimal solutions:
// 
// move coins up (1 coin drops, 13 remain) 
// move coins down 
// move coins down again (1 coin drops, 12 remain) 
// 
// 
// 2)
// {"...."
// ,".oo."
// ,".oo."
// ,"...."}
// 
// 3
// 
// Returns: -1
// 
// It is impossible to make the number of remaining coins exactly 3.
// 
// 3)
// {"......."
// ,"..ooo.."
// ,"ooooooo"
// ,".oo.oo."
// ,"oo...oo"}
// 
// 12
// 
// Returns: 4
// 
// 
// 
// 4)
// {"................."
// ,".ooooooo...oooo.."
// ,".ooooooo..oooooo."
// ,".oo.......oo..oo."
// ,".oo.......oo..oo."
// ,".ooooo.....oooo.."
// ,".ooooooo...oooo.."
// ,".....ooo..oo..oo."
// ,"......oo..oo..oo."
// ,".ooooooo..oooooo."
// ,".oooooo....oooo.."
// ,"................."}
// 
// 58
// 
// Returns: 6
// 
// 
// 
// END KAWIGIEDIT TESTING




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