hkbt

 avatar
duyvan
plain_text
a year ago
3.2 kB
4
Indexable
#include <iostream>

using namespace std;

typedef pair<int, int> ii;

#define ll long long
#define mp make_pair
#define nmax 6

const int xc[4] = {0, 1, 0, -1};
const int yc[4] = {1, 0, -1, 0};
const int n = 4;

typedef pair<int, bool> ib;

const int pw = 18;
const int po2[pw] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072};

struct Board {
	int a[nmax][nmax];

	bool inboard(int u, int v) {
		return ((u > 0) && (u <= n) && (v > 0) && (v <= n));
	}

	ib swipe(int dir) {
		int mx = 0;
		bool change = false;

		bool allUniq = true;
		int tmp = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) {
				if (a[i][j] == 0) continue;
				if ((tmp & a[i][j]) == tmp) {
					allUniq = false;
					goto label1;
				} else {
					tmp = tmp & a[i][j];
				}
			}
		label1:;
		if (allUniq) {
			return mp(0, false);
		}

		int u = 0, v = 0;
		switch (dir) {
		case 0:
			u = 1; v = 1; break;
		case 1:
			u = 1; v = 1; break;
		case 2:
			u = 1; v = n; break;
		case 3:
			u = n; v = 1; break;
		}

		while (inboard(u, v)) {
			int x = u, y = v;
			int curX = x, curY = y;
			int prvX = 0, prvY = 0;

			while (inboard(x, y)) {
				if (a[x][y] == 0) goto label2;
				
				if ((prvX == 0) && (prvY == 0)) {
					prvX = x; prvY = y;
					goto label2;
				}

				if (a[x][y] == a[prvX][prvY]) {
					a[curX][curY] = a[x][y] + a[x][y];
					mx = max(mx, a[curX][curY]); change = true;
					prvX = 0; prvY = 0;
				} else {
					if ((curX != prvX) || (curY != prvY)) change = true;

					a[curX][curY] = a[prvX][prvY];
					mx = max(mx, a[curX][curY]);
					prvX = x; prvY = y;
				}
				curX += xc[dir]; curY += yc[dir];

				label2:;
				x += xc[dir]; y += yc[dir];
			}

			if ((prvX != 0) && (prvY != 0)) {
				if ((curX != prvX) || (curY != prvY)) change = true;

				a[curX][curY] = a[prvX][prvY];
				mx = max(mx, a[curX][curY]);
				curX += xc[dir]; curY += yc[dir];
			}

			while (inboard(curX, curY)) {
				if (a[curX][curY] != 0) change = true;

				a[curX][curY] = 0;
				curX += xc[dir]; curY += yc[dir];
			}

			if (dir % 2) v++;
			else u++;
		}

		return mp(mx, change);
	}

	void print() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) cout << a[i][j] << ' ';
			cout << '\n';
		}
		cout << '\n';
	}
};

#define kmax 15

Board brd[kmax];
int k, res, bst;

void doIt(int x) {
	for (int i = 0; i < 4; i++) {
		brd[x] = brd[x - 1];

		ib rs = brd[x].swipe(i);
		if (!rs.second) continue;

		res = max(res, rs.first);
		if (res == bst) return;

		if (x < k) doIt(x + 1);
		if (res == bst) return;
	}
}

void proc() {
	int tg = 0;

	cin >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			cin >> brd[0].a[i][j];
			tg += brd[0].a[i][j];
		}

	bst = 0;
	for (int i = 0; i < pw; i++)
		if (tg >= po2[i]) bst = po2[i];
		else break;

	res = 0;
	doIt(1);
	cout << res << '\n';
}

int main() {
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	int t; cin >> t;
	for (int i = 1; i <= t; i++) {
		cout << '#' << i << ' ';
		proc();
	}
	return 0;
}
Editor is loading...
Leave a Comment