weather forecast[pku2044].cpp

PKU 上的几个题目 Tunnel Warfare Unique Solution Washing Clothes Weather Forecast Who Gets the Most Ca

// PKU 2044
// dfs with compressed state
#include <iostream>
#include <string>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
typedef long long bigint;

const int NMAX = 366;
const int LMAX = 16;
bool day[NMAX][LMAX];
int bday[NMAX];
int n;
bool hash[366][9][3200]; 

int dir[5][2] = {
	{0,1},{1,0},{0,2},{2,0},{0,0}
};

int get_val() {
	int ret = 0;
	char ch;
	while ((ch=getchar()) > '9' || ch < '0') ;
	do {
		ret = ret*10 + ch - '0';
	} while ((ch=getchar()) <= '9' && ch >= '0') ;
	return ret;
}

inline bool is_ok(short x, short y, short d)
{
	int fp = 4*x + y;
	int pos = (1<<fp) | (1<<(fp+1)) | (1<<(fp+4)) | (1<<(fp+5));
	if (bday[d] & pos)
		return false;
	return true;
}

inline bool is_rain(bigint & s, short x, short y)
{
	int i, j;
	int tx, ty;
	bigint gap = 0x7;
	for (i=tx=0; tx<4; tx++)
	{
		for (ty=0; ty<4; ty++,gap<<=3,i+=3)
		{
			bigint t = (s & gap) >> i;
			s &= ~gap;
			short gx = tx - x;
			short gy = ty - y;
			if ((gx<0||gx>1) || (gy<0||gy>1))
			{
				t ++;
				if (t > 6)
					return false;
				else
				{
					t <<= i;
					s |= t;
				}
			}
		}
	}
	return true;
}

inline int cal_path(int p, short d)
{
	p = (p*5) % 3125;
	p += d;
	return p;
}

inline bool make_hash(short d, short x, short y, int path)
{
	int pos = 3*x + y;
	if (hash[d][pos][path])
		return false;
	hash[d][pos][path] = true;
	return true;
}

bool dfs(short x, short y, short d, bigint state, int path)
{
	int i, j;

	if (d >= n)
		return true;

	for (i=0; i<5; i++)
	{
		short tx = (x + dir[i][0]) % 3;
		short ty = (y + dir[i][1]) % 3;
		if ( is_ok(tx, ty, d) )
		{
			bigint ns = state;
			if ( is_rain(ns, tx, ty) )
			{
				int np = cal_path(path, i);
				//printf("%d, %d\n", d,i);
				if ( make_hash(d, tx, ty, np) && dfs(tx, ty, d+1, ns, np) )
					return true;
			}
		}
	}
	return false;
}

int solve()
{
	int i, j, k, c;

	memset(hash, false, sizeof(hash));
	if (! is_ok(1, 1, 0) )
		return 0;
	bigint ns = 0;
	is_rain(ns, 1, 1);
	make_hash(0, 1, 1, 0);

	return dfs(1, 1, 1, ns, 0) ? 1 : 0;
}

int main()
{
	int i, j, cnt;
	while (n = get_val())
	{
		for (i=0; i<n; i++)
		{
			bday[i] = 0;
			for (j=0; j<16; j++)
			{
				day[i][j] = get_val();
				bday[i] |= (day[i][j] << j);
			}
		}

		printf("%d\n", solve());
		//printf("%d\n", tst);
	}
}