DirectionBoard.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 DirectionBoard
{
public:
	int getMinimum(vector <string> board);
};

int DirectionBoard::getMinimum (vector <string> board) 
{
	int ret;
	
	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;
	DirectionBoard *obj;
	int answer;
	obj = new DirectionBoard();
	clock_t startTime = clock();
	answer = obj->getMinimum(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[] = {"RRRD","URDD","UULD","ULLL"};
			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[] = {"RRRD","URLL","LRRR"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 2;
	all_right = KawigiEdit_RunTest(1, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	string t0[] = {"RRD","URD","ULL"};
			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[] = {"ULRLRD","UDDLRR"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 4;
	all_right = KawigiEdit_RunTest(3, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	string t0[] = {"UDLRLDLD","DLDLLDLR","LLLLLDLD","UUURRRDD"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 9;
	all_right = KawigiEdit_RunTest(4, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	string t0[] = {"UDUDUUDUDUDUDUR","LLLLDUUDRDLUDRU","DLLDLDURDURUDDL","UDUDUUDUDUDUDUR","LLLLDUUDRDLUDRU","DLLDLDURDURUDDL","UDUDUUDUDUDUDUR","LLLLDUUUDDLUDRU","DLLDLDURDURUDDL","UDUDUUDUDUDUDUR","LLLLDUUDRDLUDRU","DLLDLDURDURUDDL","UDUDUUDUDUDUDUR","LLLLDUUDRDLUDRU","RRRDLDURDURUDDR"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 73;
	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
// A direction board is a matrix filled with arrows. Each arrow occupies one cell and points in one of the four directions: left, right, down, up. Each cell has two coordinates (row, column), starting with (0, 0) in the top left corner. Given a starting cell (r, c), you can move through the board in the following way. First, check the arrow in cell (r, c). If it points left, move left of the current cell, i.e. into cell(r, c - 1). For the right arrow, move to (r, c + 1). Up goes to (r - 1, c) and down to (r + 1, c). Each row and column of the board is cyclic, so whenever the new cell is outside the board, you appear on the other side. For example, moving left from (3, 0) on a board of size 5 by 5 results in appearing in cell (3, 4).
// 
// You need a board such that for every starting cell you always return to it during the movement process. If the given board does not satisfy this condition, you can change the direction of the arrow in any cell. For example, look at the following boards. In the left one, one only returns to the initial cell when he begins in cells (1, 1), (1, 2), (2, 0), (2, 3). After redirecting two arrows, you obtain a board with the given property.
// 
// 
// 
// Find the minimum number of arrow redirections which transforms the given board into a valid one.
// 
// DEFINITION
// Class:DirectionBoard
// Method:getMinimum
// Parameters:vector <string>
// Returns:int
// Method signature:int getMinimum(vector <string> board)
// 
// 
// CONSTRAINTS
// -board will contain between 1 and 15 elements, inclusive.
// -Each element of board will contain between 1 and 15 characters, inclusive.
// -All elements of board will be of the same length.
// -Each element of board will consist of characters from the set {'L', 'R', 'U', 'D'} only.
// 
// 
// EXAMPLES
// 
// 0)
// {"RRRD",
//  "URDD",
//  "UULD",
//  "ULLL"}
// 
// Returns: 0
// 
// This board is already good. No matter which cell you start in, you always you return to it.
// 
// 1)
// {"RRRD",
//  "URLL",
//  "LRRR"}
// 
// Returns: 2
// 
// The example from the problem statement.
// 
// 2)
// {"RRD",
//  "URD",
//  "ULL"}
// 
// Returns: 2
// 
// This board is not valid, because if one starts from (1, 1), he never returns to this cell. A possible solution with only two changes:
// 
// 
// 
// 3)
// {"ULRLRD",
//  "UDDLRR"}
// 
// Returns: 4
// 
// 
// 
// 4)
// {"UDLRLDLD",
//  "DLDLLDLR",
//  "LLLLLDLD",
//  "UUURRRDD"}
// 
// Returns: 9
// 
// 
// 
// 5)
// {"UDUDUUDUDUDUDUR",
//  "LLLLDUUDRDLUDRU",
//  "DLLDLDURDURUDDL",
//  "UDUDUUDUDUDUDUR",
//  "LLLLDUUDRDLUDRU",
//  "DLLDLDURDURUDDL",
//  "UDUDUUDUDUDUDUR",
//  "LLLLDUUUDDLUDRU",
//  "DLLDLDURDURUDDL",
//  "UDUDUUDUDUDUDUR",
//  "LLLLDUUDRDLUDRU",
//  "DLLDLDURDURUDDL",
//  "UDUDUUDUDUDUDUR",
//  "LLLLDUUDRDLUDRU",
//  "RRRDLDURDURUDDR"}
// 
// 
// Returns: 73
// 
// 
// 
// END KAWIGIEDIT TESTING

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