zju2125_std.cpp

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

#include <iostream>
#include <memory>
#include <set>

using namespace std;

#define for if(0); else for

const int PipeOuts[5][4] = {{0}, {5, 10}, {3, 6, 12, 9}, {7, 14, 13, 11}, {15}};
const int PipeTypes[5] = {1, 2, 4, 4, 1};

struct node
{
	char Classes[9];
	short Rights, RightFires;
	bool Down, DownFire;
};

struct node_less
{
	bool operator()(node* A, node* B) const
	{
		return memcmp(A, B, sizeof(node)) < 0;
	}
};

typedef set<node*, node_less> hash;

int Sour;
int Blocks[9][6];
int Length;
node Queue[800000];
int PCursor, PLength;
node PQueue[800000];
hash Hash;
int MaxTotal;

inline bool get(int V, int X)
{
	return (V >> X) & 1;
}

bool initialize()
{
	if (!(cin >> Sour)) return false;
	Sour--;
	for (int X = 0; X < 9; X++) for (int Y = 0; Y < 6; Y++)
	{
		char Ch;
		cin >> Ch;
		if (Ch == '.') Blocks[X][Y] = 0;
		else if (Ch == '-') Blocks[X][Y] = 1;
		else if (Ch == 'L') Blocks[X][Y] = 2;
		else if (Ch == 'T') Blocks[X][Y] = 3;
		else Blocks[X][Y] = 4;
	}
	return true;
}

inline void make_lone(node& Node, int X)
{
	if (Node.Classes[X] != X) Node.Classes[X] = X;
	else
	{
		int XX;
		for (XX = X + 1; XX < 9; XX++)
			if (Node.Classes[XX] == X) break;
		for (int XXX = XX; XXX < 9; XXX++)
			if (Node.Classes[XXX] == X) Node.Classes[XXX] = XX;
	}
}

inline void make_fire(node& Node, int X)

{
	int XX = Node.Classes[X];
	for (int XXX = XX; XXX < 9; XXX++)
		if (Node.Classes[XXX] == XX)
		{
			Node.Classes[XXX] = XXX;
			if (get(Node.Rights, XXX)) Node.RightFires |= 1 << XXX;
		}
}

inline void make_unite(node& Node, int X1, int X2)
{
	int Old = Node.Classes[X1];
	int New = Node.Classes[X2];
	if (Old < New)
	{
		int Temp = Old;
		Old = New;
		New = Temp;
	}
	for (int XX = 0; XX < 9; XX++)
		if (Node.Classes[XX] == Old)
			Node.Classes[XX] = New;
}

inline int count_ones(int V)
{
	int Result = 0;
	while (V > 0) Result += V % 2, V /= 2;
	return Result;
}

void solve()
{
	Length = 1;
	for (int I = 0; I < 9; I++)
		Queue[0].Classes[I] = I;
	Queue[0].Rights = Queue[0].RightFires = 1 << Sour;
	Queue[0].Down = Queue[0].DownFire = false;
	for (int Y = 0; Y < 6; Y++) for (int X = 0; X < 9; X++)
	{
		int BestCursor = -1;
		int BestRightFires = 0;
		bool BestDownFire = false;
		for (int I = 0; I < Length; I++)
		{
			int RightFires = Queue[I].RightFires;
			bool DownFire = Queue[I].DownFire;
			if ((RightFires & BestRightFires) == BestRightFires &&
				(RightFires > BestRightFires || DownFire))
			{
				BestCursor = I;
				BestRightFires = RightFires;
				BestDownFire = DownFire;
			}
		}
		PLength = Length;
		memcpy(PQueue, Queue, Length * sizeof *Queue);
		Length = 0;
		Hash.clear();
		int Type = Blocks[X][Y];
		for (int Rotated = 0; Rotated < PipeTypes[Type]; Rotated++)
		{
			bool Outs[4];
			for (int Dir = 0; Dir < 4; Dir++)
				Outs[Dir] = get(PipeOuts[Type][Rotated], Dir);
			for (PCursor = 0; PCursor < PLength; PCursor++)
			{
				node Node = PQueue[PCursor];
				if (PCursor != BestCursor &&
					(BestRightFires & Node.Rights) == Node.Rights &&
					BestDownFire >= Node.Down)
					continue;
				bool Fired = false;
				bool Down = Outs[2] && X < 9 - 1;
				// assumed:
				// if a block is fired, it must be lone
				// if a block can not go right or down, it must be lone
				// optional: if a block is lone and nonfired, it must not go out to only one direction
				if (!get(Node.Rights, X) || !Outs[3])
				{
					make_lone(Node, X);
					if (Node.Down && Outs[0])
						if (Node.DownFire) // block X - 1 must be lone
							Fired = true;
						else
							if (Down || Outs[1])
								Node.Classes[X] = Node.Classes[X - 1];
				}
				else
				{
					Fired = get(Node.RightFires, X);
					if (!Node.Down || !Outs[0])
					{
						if (!Down && !Outs[1]) make_lone(Node, X);
					}
					else
					{
						Fired |= Node.DownFire;
						if (get(Node.RightFires, X))
							if (Node.DownFire)
								;
							else
								make_fire(Node, X - 1);
						else
							if (Node.DownFire)
								make_fire(Node, X);
							else
							{
								make_unite(Node, X - 1, X);
								if (!Down && !Outs[1])
									make_lone(Node, X);
							}
					}
				}
				if (X > 0 && !get(Node.Rights, X - 1))
					make_lone(Node, X - 1);
				if (Outs[1]) Node.Rights |= 1 << X;
				else Node.Rights &= ~(1 << X);
				if (Down) Node.Down = true;
				else Node.Down = false;
				if (Fired && Outs[1]) Node.RightFires |= 1 << X;
				else Node.RightFires &= ~(1 << X);
				if (Fired && Down) Node.DownFire = true;
				else Node.DownFire = false;
				bool Lones[9];
				for (int I = 0; I < 9; I++)
					if (Node.Classes[I] == I)
						Lones[I] = true;
					else
						Lones[I] = Lones[Node.Classes[I]] = false;
				for (int I = X - 1; I <= X; I++)
					if (I == X)
						if (Lones[I] && !get(Node.RightFires, I) && !Node.DownFire && !(Node.Down && get(Node.Rights, I)))
							Node.Down = false,
							Node.Rights &= ~(1 << I);
						else;
					else
						if (Lones[I] && !get(Node.RightFires, I))
							Node.Rights &= ~(1 << I);
				Queue[Length] = Node;
				if ((Node.RightFires != 0 || Node.DownFire) &&
					Hash.insert(&Queue[Length]).second)
					Length++;
			}
		}
	}
	MaxTotal = 0;
	for (int I = 0; I < Length; I++)
	{
		int Total = count_ones(Queue[I].RightFires);
		if (Total > MaxTotal) MaxTotal = Total;
	}
}

int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.std","w",stdout);
	while (initialize())
	{
		solve();
		cout << MaxTotal << endl;
	}
	return 0;
}