2265.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2265 on 2006-06-06 at 01:33:39 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int SN = 128, EN = 16384;
const int DIR[][2] = { { 0, 1 }, { 1, 0 }, { 1, 1 } };

vector<int> type[EN];
int set[EN], ele[EN], blk[EN], bn, n;
char mat[SN][SN];
bool vst[EN];

bool same(int, int);

int main()
{
	int t, T, i, j, k, l;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n); bn = 0;
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) blk[bn++] = (n-i)*n-1-j;
		memset(vst, true, sizeof(vst));
		int tn = 0;
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) {
				scanf("\n%c", &mat[i][j]);
				for(k = 0; k < tn; k++) {
					int x = ele[k] >> 7, y = ele[k] & 127;
					if(mat[i][j] == mat[x][y]) break;
				}
				int cd = (i<<7) | j;
				if(k == tn) { vst[k] = false; bn--; ele[tn++] = cd; type[k].clear(); }
				set[cd] = k; type[k].push_back(cd);
			}
		if(tn == n*n) { printf("0\n"); continue; }
		for(i = 2; i < n; i++) {
			int nst[EN], xn = tn;
			for(j = 0; j < xn; j++) {
				int m = type[j].size(), b;
				for(b = k = 0; k < m; k++) {
					int e = type[j][k], x = e>>7, y = e&127;
					if(x > n-i || y > n-i) { type[j][k--] = type[j][--m]; type[j].pop_back(); continue; }
					else if(b == 0) { ele[b++] = e; nst[e] = j; continue; }
					for(l = 0; l < b; l++)
						if(same(ele[l], e)) break;
					if(l == b) { ele[b++] = e; nst[e] = blk[--bn]; vst[blk[bn]] = false; type[tn++].clear(); }
					else nst[e] = nst[ele[l]];
					if(nst[e] != j) 
						{ type[j][k--] = type[j][--m]; type[j].pop_back(); type[nst[e]].push_back(e); }
				}
				if(m == 0 && !vst[j]) { blk[bn++] = j; vst[j] = true; }
			}
			if(n*n-bn == (n-i+1)*(n-i+1)) break;
			memcpy(set, nst, sizeof(nst));
		}
		printf("%d\n", i-1);
	}

	return 0;
}

bool same(int a, int b)
{
	int i, ax = a>>7, ay = a&127, bx = b>>7, by = b&127;
	for(i = 0; i < 3; i++) {
		int nax = ax+DIR[i][0], nay = ay+DIR[i][1], nbx = bx+DIR[i][0], nby = by+DIR[i][1];
		if(set[(nax<<7)|nay] != set[(nbx<<7)|nby]) return false;
	}
	return true;
}