StarAdventure.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <cassert>
#include <sstream>
#include <set>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <time.h>
using namespace std;
/* https://www.topcoder.com/stat?c=problem_statement&pm=2940&rd=5854 */

#define SIZEOFSTRINGARRAY(s) sizeof(s)/sizeof(s[0])

class StarAdventure
{
private:
	vector<string> mLevel;
	int mHeight, mWidth;
	int getMostStars(int x1, int y1, int x2, int y2, int x3, int y3);
public:
	int mostStars(vector<string> level);
};
int memo[101][50][50][50];
int StarAdventure::getMostStars(int x1, int y1, int x2, int y2, int x3, int y3)
{
	if (x1 >= mHeight || y1 >= mWidth ||
			x2 >= mHeight || y2 >= mWidth ||
			x3 >= mHeight || y3 >= mWidth)
		return 0;
	int &mem = memo[x2+y2][y1][y2][y3];
	if (mem) return mem;

	int ret = mLevel[x1][y1] - '0';
	if (make_pair(x1, y1) != make_pair(x2, y2))
		ret += mLevel[x2][y2] - '0';
	if (make_pair(x1, y1) != make_pair(x2, y2) && make_pair(x1, y1) != make_pair(x3, y3) && make_pair(x2, y2) != make_pair(x3, y3))
		ret += mLevel[x3][y3] - '0';
	int add = 0;
	for (int i = 0; i < 2; ++i)
	{
		for (int j = 0; j < 2; ++j)
		{
			for (int k = 0; k < 2; ++k)
			{
				add = std::max(add, getMostStars(i ? x1 + 1: x1, i ? y1: y1 + 1,
												j ? x2 + 1: x2, j ? y2: y2 + 1,
												k ? x3 + 1: x3, k ? y3 : y3 + 1));
			}
		}
	}

	ret += add;
	mem = ret;
	return ret;
}

int StarAdventure::mostStars(vector<string> level)
{
	mLevel = level;
	mHeight = level.size();
	mWidth = level[0].size();

	return getMostStars(0, 0, 0, 0, 0, 0);
}

void TEST(vector<string> levels, int expected)
{
	memset(memo, 0, sizeof(memo));
    clock_t start, end;
    double cpu_time_used;
    
    start = clock();
    StarAdventure starAdventure;
    
	int result = starAdventure.mostStars(levels);
    
	assert( result == expected );
    
    end = clock();
    cpu_time_used = ((double) (end - start));
    cout<<"Time taken : "<<cpu_time_used<<endl;
}

vector<string> convert(string *list, int n)
{
    vector<string> ret;
    
    for (int i = 0; i< n; ++i)
    {
        ret.push_back(list[i]);
    }
    
    return ret;
}

void Test1()
{
    string test[] = {"01", "11"};
    
    TEST(convert(test, SIZEOFSTRINGARRAY(test)), 3);
}

void Test2()
{
    string test[] = {"012"
,"012"
,"012"
,"012"
,"012"
,"012"
,"012"}
;
    
    TEST(convert(test, SIZEOFSTRINGARRAY(test)), 21);
}

void Test3()
{
    string test[] = {"0999999999"
,"9999999999"
,"9999999999"
,"9999999999"
,"9999999999"
,"9999999999"
,"9999999999"
,"9999999999"
,"9999999999"
,"9999999999"};
    
    TEST(convert(test, SIZEOFSTRINGARRAY(test)), 450);
}

void Test4()
{
	string test[] = {"0123456789",
 "1123456789",
 "2223456789",
 "3333456789",
 "4444456789",
 "5555556789",
 "6666666789",
 "7777777789",
 "8888888889",
 "9999999999"};
    TEST(convert(test, SIZEOFSTRINGARRAY(test)), 335);
}

void Test5()
{
	string test[] = {"0661584547", "7864938010", "5505660579", "2806562308", "1440555977", "2800114662", "1547303097", "6420937820", "7534381930", "5345354737"};

	TEST(convert(test, SIZEOFSTRINGARRAY(test)), 283);
}

void Test6()
{
	string test[] = {"01296289856427627583990950344462777968520299686111", "43022678573840646287258869226707798201798017874000", "99091250801748059146336878382798759607881205562137", "11816984638204727415560787687605639156017897697531", "40661158878887808386818330156139353870554316450915", "87052499187460711490688086746167081362791796225002", "01947863172930252103852068986869791124194119575635", "99375048221224116088159793256443275472445959843964", "11665386993007983373118551550102818759574894279931", "48090805426836021383141239785757526046731211113294", "86931124195333229447180226612761828264433017855583", "43007800221674000083556754623498399774267936433906", "21078141359092519508025805250847051837138333400353", "69814044543738406683645653644949538893806585184212", "33943151758342660866144437241447718020681869707123", "50243078184094857523180809090799328330438402374985", "08566426434568208825612408902362449478270237075064", "71533000131548124383962607058956508620811039545105", "20341652438371053718985796928981187335294991655455", "32591191176597647230235331857688048952376257444637", "16582644947654229541198086173371469690934326060339", "43124097437898104373318455127213940834699361055691", "62109725462158969293897516214824651754684697404632", "41354365968573108227159781544593511305624482527810", "56772548929537378930633648170871233448838613375608", "72932196280118065569902687908277689193692143155132", "36554232324581780762499044939284712416311431013315", "43918362809584311849172602638378407054514114668570", "26606123807258572332229875931079192203431543536195", "04108170620211326072873780115311132179461595475354", "94430952267345272347039904716259706352013871176173", "33286418782466966674782766282825306942997293358752", "23880255384711981372172273791039195381990304632705", "92532741675774493706512349230175416748421110202957", "35004464257114530864401047389205307624260455200898", "17950825896557004718010946951249401962969911683288", "67785299551575462998432452665773214861922053784778", "43774869214514650029563681659442559622835580708379", "17475976964086926143045639786515703547681091892581", "85504670738884583411475863522218063584869461958175", "89296969879850466941406364976282304903284232178276", "61851183935100918229914862281948792834737254946936", "84428201578927374215319915034895892723100107765542", "23452740367308898111237986434700239035719988453296", "27395691783361182628932624730123659384639699682261", "27017054390616715972814318569994425773869622949666", "45724534900418807729724328199044963573348604952485", "57360759001656212967724321892346348019285322384403", "78453823856605885318254243089144862775794590108155", "65543037571824365816297258726224394890459038188189"};
    TEST(convert(test, SIZEOFSTRINGARRAY(test)), 1898);
}

void Test7()
{
}

int main()
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    Test7();
    cout<<"success";
    
    getchar();
    return 0;
}