Submission #25932859

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int A[4][4];
int B[4][4];

int uf[17];

int root(int p) {
	return uf[p] < 0 ? p : (uf[p] = root(uf[p]));
}

bool join(int p, int q) {
	p = root(p);
	q = root(q);
	if (p == q) return false;
	uf[p] += uf[q];
	uf[q] = p;
	return true;
}

int dy[] = {-1, 0, 1, 0};
int dx[] = {0, -1, 0, 1};

int main()
{
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			scanf("%d", &(A[i][j]));
		}
	}

	int ans = 0;
	for (int mask = 0; mask < (1 << 16); ++mask) {
		bool isok = true;
		for (int y = 0; y < 4; ++y) {
			for (int x = 0; x < 4; ++x) {
				B[y][x] = (mask >> (y * 4 + x)) & 1;
				if (A[y][x] && !B[y][x]) isok = false;
			}
		}
		if (!isok) continue;

		for (int y = 1; y < 4; ++y) {
			for (int x = 1; x < 4; ++x) {
				if (B[y - 1][x - 1] && B[y][x] && !B[y - 1][x] && !B[y][x - 1]) isok = false;
				if (!B[y - 1][x - 1] && !B[y][x] && B[y - 1][x] && B[y][x - 1]) isok = false;
			}
		}

		for (int i = 0; i < 17; ++i) uf[i] = -1;
		int n_grp = 17;
		for (int y = 0; y < 4; ++y) {
			for (int x = 0; x < 4; ++x) {
				for (int d = 0; d < 4; ++d) {
					int y2 = y + dy[d];
					int x2 = x + dx[d];

					if (B[y][x] && 0 <= y2 && y2 < 4 && 0 <= x2 && x2 < 4 && B[y2][x2]) {
						if (join(y * 4 + x, y2 * 4 + x2)) --n_grp;
					} else if (!B[y][x]) {
						if (0 <= y2 && y2 < 4 && 0 <= x2 && x2 < 4) {
							if (!B[y2][x2]) {
								if (join(y * 4 + x, y2 * 4 + x2)) --n_grp;
							}
						} else {
							if (join(y * 4 + x, 16)) --n_grp;
						}
					}
				}
			}
		}
		if (n_grp == 2) ++ans;
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result