zoj1740.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <algorithm>
#include <set>
using namespace std;

long long getnum(int grids[4][4]){
	static int i,j;
	long long ans=0;
	for (i = 0; i < 4; ++i)
		for (j = 0; j < 4; ++j){
			ans <<= 3;
			ans += grids[i][j];
		}
	return ans;
}

void getgrid(int grids[4][4],long long num){
	static int i,j;
	for (i = 3; i>-1; --i)
		for (j = 3; j >- 1; --j){
			grids[i][j] = num & 7;
			num >>= 3;
		}
}

struct elem{
	int x,y;
	long long st;
	elem(const int &xx=0,const int &yy=0,const long long &ss=0):x(xx),y(yy),st(ss){}
};

bool operator<(const elem &a,const elem &b)
{
	if (a.x!=b.x) return a.x<b.x;
	if (a.y!=b.y) return a.y<b.y;
	return a.st<b.st;
}

set<elem> last,curr;

int drys[370][4][4];
int n;

bool input()
{
	scanf("%d",&n);
	if (n==0) return 0;
	int i,j,k;
	for (i=0;i<n;++i)
		for (j=0;j<4;++j)
			for (k=0;k<4;++k)
				scanf("%d",&drys[i][j][k]);
	return 1;
}

bool isvalid(const int &x,const int &y)
{
	return x>-1&&x<3&&y>-1&&y<3;
}

const int cx[]={0,1,0,-1},cy[]={1,0,-1,0};

bool judge(const int &ds,const int &x,const int &y,int grids[4][4]){
	static int i,j;
	for (i = 0; i < 2; ++i)
		for (j = 0; j < 2; ++j)
			if (drys[ds][x+i][y+j]) return 0;
	for (i = 0; i < 4; ++i)
		for (j = 0; j < 4; ++j){
			if (grids[i][j]==5 && !(i-x>=0&&i-x<2)&&!(j-y>=0&&j-y<2)) return 0;
			if (grids[i][j]==5 && !(i-x>=0&&i-x<2&&j-y>=0&&j-y<2)&&drys[ds+1][i][j]) return 0;
		}
	return 1;
}

bool test(int grids[4][4]){
	static int i,j;
	for (i = 0; i < 4; ++i)
		for (j = 0;j < 4; ++j)
			if (grids[i][j] > 6) return 0;
	return 1;
}

bool dp(){
	curr.clear();
	curr.insert(elem(1,1,0));
	int i,j,k,x,y,d,r,bx,by,tx,ty;
	long long s;
	int lgrids[4][4],cgrids[4][4];
	set<elem>::iterator iter;
	bool flag;
	for (i=0;i<n&&curr.size();++i)
	{
		last=curr;
		curr.clear();
		for (iter=last.begin();iter!=last.end();++iter)
		{
			x=(*iter).x;
			y=(*iter).y;
			getgrid(lgrids,(*iter).st);
			if (judge(i,x,y,lgrids))
			{
				for (bx=0;bx<4;++bx)
					for (by=0;by<4;++by)
						cgrids[bx][by]=lgrids[bx][by]+1;
				for (bx=0;bx<2;++bx)
					for (by=0;by<2;++by)
						cgrids[x+bx][y+by]=0;
				if (test(cgrids)) curr.insert(elem(x,y,getnum(cgrids)));
			}
			if (i>0)
			{
				for (d=0;d<4;++d)
					for (r=1;r<3;++r)
					{
						tx=x+cx[d]*r;
						ty=y+cy[d]*r;
						if (isvalid(tx,ty)&&judge(i,tx,ty,lgrids))
						{
							for (bx=0;bx<4;++bx)
								for (by=0;by<4;++by)
									cgrids[bx][by]=lgrids[bx][by]+1;
							for (bx=0;bx<2;++bx)
								for (by=0;by<2;++by)
									cgrids[tx+bx][ty+by]=0;
							if (test(cgrids)) curr.insert(elem(tx,ty,getnum(cgrids)));
						}
					}
			}
		}
	}
	return curr.size()>0;
}

int main(){
	while (input())
		if (dp()) printf("1\n");
		else printf("0\n");
	return 0;
}