Submission #138607

#	Time	Username	Problem	Language	Result	Execution time	Memory
138607		KCSC	Tetris (COCI17_tetris)	C++14	80 / 80	2 ms	376 KiB

tetris

#include <bits/stdc++.h>
using namespace std;

struct Figure {
	int n, m, a[4][4];
} fig[11];

int cnt[5];
char mat[11][11];
bool oki[11][11];

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

const int aux[11][4][4] = {
{ {1, 1, 0, 0},
	{1, 1, 0, 0},
	{0, 0, 0, 0},
	{0, 0, 0, 0} }
,
{ {1, 1, 1, 1},
	{0, 0, 0, 0},
	{0, 0, 0, 0},
	{0, 0, 0, 0} }
,
{ {1, 0, 0, 0},
  {1, 0, 0, 0},
  {1, 0, 0, 0},
  {1, 0, 0, 0} }
,
{ {0, 1, 1, 0},
	{1, 1, 0, 0},
	{0, 0, 0, 0},
	{0, 0, 0, 0} }
,
{ {1, 0, 0, 0},
	{1, 1, 0, 0},
	{0, 1, 0, 0},
	{0, 0, 0, 0} }
,
{ {1, 1, 0, 0},
	{0, 1, 1, 0},
	{0, 0, 0, 0},
	{0, 0, 0, 0} }
,
{ {0, 1, 0, 0},
	{1, 1, 0, 0},
	{1, 0, 0, 0},
	{0, 0, 0, 0} }
,
{ {0, 1, 0, 0},
	{1, 1, 1, 0},
	{0, 0, 0, 0},
	{0, 0, 0, 0} }
,
{ {0, 1, 0, 0},
	{1, 1, 0, 0},
	{0, 1, 0, 0},
	{0, 0, 0, 0} }
,
{ {1, 1, 1, 0},
	{0, 1, 0, 0},
	{0, 0, 0, 0},
	{0, 0, 0, 0} }
,
{ {1, 0, 0, 0},
	{1, 1, 0, 0},
	{1, 0, 0, 0},
	{0, 0, 0, 0} }
};

void fill(int x, int y, int n, int m, int &mnx, int &mxx, int &mny, int &mxy) {
	oki[x][y] = true;
	mnx = min(mnx, x); mxx = max(mxx, x);
	mny = min(mny, y); mxy = max(mxy, y);
	for (int d = 0; d < 4; ++d) {
		int xx = x + dx[d], yy = y + dy[d];
		if (xx < 1 or xx > n or yy < 1 or yy > m or oki[xx][yy] or mat[xx][yy] != mat[x][y])
			continue;
		fill(xx, yy, n, m, mnx, mxx, mny, mxy);
	}
}

bool good(int mnx, int mxx, int mny, int mxy, int it, char ch) {
	if (fig[it].n != mxx - mnx + 1)
		return false;
	if (fig[it].m != mxy - mny + 1)
		return false;
	for (int i = mnx; i <= mxx; ++i) 
		for (int j = mny; j <= mxy; ++j)
			if (fig[it].a[i - mnx][j - mny] != (mat[i][j] == ch))
				return false;
	return true;
}

int main(void) {
#ifdef HOME
	freopen("tetris.in", "r", stdin);
	freopen("tetris.out", "w", stdout);
#endif
	for (int i = 0; i < 11; ++i) 
		memcpy(fig[i].a, aux[i], sizeof aux[i]);
	fig[0].n = 2; fig[0].m = 2;
	fig[1].n = 1; fig[1].m = 4;
	fig[2].n = 4; fig[2].m = 1;
	fig[3].n = 2; fig[3].m = 3;
	fig[4].n = 3; fig[4].m = 2;
	fig[5].n = 2; fig[5].m = 3;
	fig[6].n = 3; fig[6].m = 2;
	fig[7].n = 2; fig[7].m = 3;
	fig[8].n = 3; fig[8].m = 2;
	fig[9].n = 2; fig[9].m = 3;
	fig[10].n = 3; fig[10].m = 2;
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) 
		cin >> (mat[i] + 1);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (oki[i][j] or mat[i][j] == '.')
				continue;
			int mnx = n, mxx = 1, mny = m, mxy = 1;
			fill(i, j, n, m, mnx, mxx, mny, mxy);
			int it = 0;
			while (!good(mnx, mxx, mny, mxy, it, mat[i][j]))
				++it;
			if (it == 0)
				++cnt[0];
			else if (it >= 7)
				++cnt[4];
			else
				++cnt[(it + 1) / 2];
		}
	}
	for (int i = 0; i < 5; ++i)
		cout << cnt[i] << "\n";
	return 0;
}

• Subtask 1: 80 / 80