ColoredStrokes.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 <cstring>
using namespace std;

typedef pair<int,int> ii;

#define	SZ(a)	int((a).size())

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


class ColoredStrokes
{
public:
	int getLeast(vector <string> pic)
	{
		int ret = 0;

		ii paint[55][55];
		forn(i, 55)	forn(j, 55)	paint[i][j].first = paint[i][j].second = 0;

		forn(i, SZ(pic))
		{
			forn(j, pic[i].length())
			{
				if(pic[i][j] == '.')	continue;

				if(pic[i][j] == 'R' )
				{
					if(paint[i][j].first !=  0)	continue;
					ret++;

					forab(k, j, pic[i].length()-1)
					{
						if(pic[i][k] == 'R' || pic[i][k] == 'G')
						{
							paint[i][k].first = ret;
						}
						else	break;
					}
				}
				else if(pic[i][j] == 'B')
				{
					if(paint[i][j].second !=  0)	continue;
					ret++;

					forab(k, i, SZ(pic) -1 )
					{
						if(pic[k][j] == 'B' || pic[k][j] == 'G')
						{
							paint[k][j].second = ret;
						}
						else	break;
					}
				}
				else if(pic[i][j] == 'G')
				{
					
					if(paint[i][j].first ==  0)	
					{
						ret++;

						forab(k, j, pic[i].length()-1)
						{
							if(pic[i][k] == 'R' || pic[i][k] == 'G')
							{
								paint[i][k].first = ret;
							}
							else	break;
						}
					}
					
					if(paint[i][j].second ==  0)
					{
						ret++;

						forab(k, i, SZ(pic) -1 )
						{
							if(pic[k][j] == 'B' || pic[k][j] == 'G')
							{
								paint[k][j].second = ret;
							}
							else	break;
						}
					}
				}
			}
		}
/*
		forn(i, SZ(pic))
		{
			forn(j, pic[i].length())
				cout << paint[i][j].first << ", " << paint[i][j].second << " \t ";
			cout << endl;
		}
*/		
		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;
	ColoredStrokes *obj;
	int answer;
	obj = new ColoredStrokes();
	clock_t startTime = clock();
	answer = obj->getLeast(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[] = {"...","..."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 0;
	all_right = KawigiEdit_RunTest(0, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	string t0[] = {"..B.","..B."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 1;
	all_right = KawigiEdit_RunTest(1, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	string t0[] = {".BB."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 2;
	all_right = KawigiEdit_RunTest(2, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	string t0[] = {"...B..",".BRGRR",".B.B.."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 3;
	all_right = KawigiEdit_RunTest(3, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	string t0[] = {"...B..",".BRBRR",".B.B.."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 4;
	all_right = KawigiEdit_RunTest(4, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	string t0[] = {"GR","BG"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 4;
	all_right = KawigiEdit_RunTest(5, 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
// Manao has a bitmap H pixels high and W pixels wide. Initially, each of the pixels is white. Manao draws several (possibly zero) horizontal and/or vertical strokes. A stroke is a line segment 1 pixel thick and 1 or more pixels long. Manao only draws horizontal strokes with red color and vertical strokes with blue. He can paint a one pixel long stroke with either red or blue color, and the stroke will be considered horizontal if red and vertical if blue. Manao never draws two horizontal or two vertical strokes that overlap. If a horizontal stroke and a vertical stroke cross, the pixel at their intersection becomes green.
// 
// You're given a vector <string> picture denoting the bitmap after Manao's drawing experiments. The x-th character of the y-th element of picture describes the color of the pixel at coordinates (x, y) of the bitmap, where (0, 0) is the pixel at the top left corner and (W-1, H-1) is the pixel at the bottom right corner.  'R' is red, 'G' is green, 'B' is blue and '.' is white. Return the least possible number of strokes needed to obtain the given picture.
// 
// DEFINITION
// Class:ColoredStrokes
// Method:getLeast
// Parameters:vector <string>
// Returns:int
// Method signature:int getLeast(vector <string> picture)
// 
// 
// CONSTRAINTS
// -picture will contain between 1 and 50 elements, inclusive.
// -Each element of picture will be between 1 and 50 characters long, inclusive.
// -All elements of picture will have equal length.
// -Each character in picture will be 'R', 'G', 'B' or '.'.
// 
// 
// EXAMPLES
// 
// 0)
// {"...",
//  "..."}
// 
// Returns: 0
// 
// The picture is blank, Manao made no strokes.
// 
// 1)
// {"..B.",
//  "..B."}
// 
// Returns: 1
// 
// A single vertical stroke is enough.
// 
// 2)
// {".BB."}
// 
// Returns: 2
// 
// Since only vertical strokes are painted with blue color, this picture needs two strokes.
// 
// 3)
// {"...B..",
//  ".BRGRR",
//  ".B.B.."}
// 
// Returns: 3
// 
// One horizontal and two vertical strokes are necessary for this masterpiece.
// 
// 4)
// {"...B..",
//  ".BRBRR",
//  ".B.B.."}
// 
// Returns: 4
// 
// This is the same picture as in the previous case with pixel (3,1) colored blue instead of green. Therefore, a single horizontal stroke won't help.
// 
// 5)
// {"GR",
//  "BG"}
// 
// Returns: 4
// 
// 
// 
// END KAWIGIEDIT TESTING
//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!yy