Artifact Content
Not logged in

Artifact 2b2cc140266eef07d33e5c0cba6f2358d271162e


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

int memo[1024][30];

class FourBlocks { public:
	int X, Y;
	vector<string> G;
	int maxScore(vector <string> grid) 
	{
		X = grid.size();
		Y = grid[0].size();
		G = grid;

		// sentinels
		for(int x=0; x<X; ++x)
			G[x] += '0';
		G.push_back( string(Y+1,'0') );

		int baseScore = 0;
		for(int x=0; x<X; ++x)
		for(int y=0; y<Y; ++y)
			baseScore += (G[x][y]=='1');

		// memoized search
		memset(memo, 0xff, sizeof(memo));
		return baseScore + best(0);
	}

	int best(int y)
	{
		if( Y <= y )
			return 0;

		int mask = 0;
		for(int x=0; x<X; ++x)
			mask |= ((G[x][y]=='.') << x);
		if( memo[mask][y] != -1 )
			return memo[mask][y];
		return memo[mask][y] = best(0, y);
	}

	int best(int x, int y)
	{
		if( X <= x )
			return best(y+1);
		int Max = 0;
		if( G[x][y]=='.' )
		{
			if( G[x+1][y]=='.' && G[x][y+1]=='.' && G[x+1][y+1]=='.' )
			{
				// can put 4
				G[x][y]=G[x+1][y]=G[x][y+1]=G[x+1][y+1] = '4';
				Max = max(Max, 16+best(x+2, y));
				G[x][y]=G[x+1][y]=G[x][y+1]=G[x+1][y+1] = '.';
			}
			// can put 1
			G[x][y] = '1';
			Max = max(Max, 1+best(x+1, y));
			G[x][y] = '.';
		}
		else
		{
			Max = max(Max, best(x+1, y));
		}
		return Max;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, FourBlocks().maxScore(grid));}
int main(){

CASE(0)
	string grid_[] = {".....1..1..",
 "..1.....1.."};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int _ = 70; 
END
CASE(1)
	string grid_[] = {"...1.",
 ".....",
 ".1..1",
 ".....",
 "1...."};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int _ = 73; 
END
CASE(2)
	string grid_[] = {"...1.",
 ".1...",
 "..1.1",
 "1...."};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int _ = 20; 
END
CASE(3)
	string grid_[] = {".....1...",
 ".....1...",
 "111111111",
 ".....1...",
 ".....1..."};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int _ = 117; 
END
CASE(4)
	string grid_[] = {".........................",
 ".........................",
 ".........................",
 ".........................",
 ".........................",
 ".........................",
 ".........................",
 ".........................",
 ".........................",
 ".........................",
 };
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int _ = 117; 
END
CASE(5)
	string grid_[] = {
 "1...", "....", "..11",
 };
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int _ = 36; 
END
CASE(6)
	string grid_[] = {
 "1..", "...", "..1", "..1",
 };
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int _ = 36; 
END

}
// END CUT HERE