Submission #570596

#	Time	Username	Problem	Language	Result	Execution time	Memory
570596		egod1537	Young Zebra (KRIII5_YZ)	C++14	0 / 7	90 ms	12004 KiB

YZ

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
#define x first
#define y second
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int ans[1201][1201];
bool vit[1201][1201], arr[1201][1201];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		string str; cin >> str;
		for (int j = 0; j < 3 * m; j++)
		{
			arr[i][j] = str[j % m] == 'B';
			arr[i+n][j] = str[j % m] == 'B';
			arr[i+2*n][j] = str[j % m] == 'B';
		}
	}
	n *= 3; m *= 3;
	for (int i = 0; i < n; i++)
	{
		if (vit[i][0]) continue;
		queue<pi> q;
		q.push({ i, 0 }); vit[i][0] = true;
		bool inf = false;
		vector<pi> vec;
		while (q.size())
		{
			pi top = q.front(); q.pop();
			vec.push_back(top);
			if (top.y == m - 1 && top.x == i)
				inf = true;
			for (int j = 0; j < 4; j++)
			{
				int nx = top.x + dx[j], ny = top.y + dy[j];
				if (nx < 0 || ny < 0 || nx >= n || ny >= m || 
					vit[nx][ny] || arr[top.x][top.y] != arr[nx][ny]) continue;
				vit[nx][ny] = true;
				q.push({nx, ny});
			}
		}
		if (inf)
			for (auto& p : vec)
				ans[p.x][p.y] = -1;
	}
	memset(vit, false, sizeof(vit));
	for (int i = 0; i < m; i++)
	{
		if (vit[0][i]) continue;
		queue<pi> q;
		q.push({ 0, i }); vit[0][i] = true;
		bool inf = false;
		vector<pi> vec;
		while (q.size())
		{
			pi top = q.front(); q.pop();
			vec.push_back(top);
			if (top.x == n - 1 && top.y == i)
				inf = true;
			for (int j = 0; j < 4; j++)
			{
				int nx = top.x + dx[j], ny = top.y + dy[j];
				if (nx < 0 || ny < 0 || nx >= n || ny >= m ||
					vit[nx][ny] || arr[top.x][top.y] != arr[nx][ny]) continue;
				vit[nx][ny] = true;
				q.push({ nx, ny });
			}
		}
		if (inf)
			for (auto& p : vec)
				ans[p.x][p.y] = -1;
	}
	memset(vit, false, sizeof(vit));
	for (int i = n/3; i < 2*n/3; i++)
	{
		for (int j = m/3; j < 2*m/3; j++)
		{
			if (ans[i][j] == -1 || vit[i][j]) continue;
			queue<pi> q;
			q.push({ i, j }); vit[i][j] = true;
			vector<pi> vec;
			while (q.size())
			{
				pi top = q.front(); q.pop();
				vec.push_back(top);
				for (int k = 0; k < 4; k++)
				{
					int nx = top.x + dx[k], ny = top.y + dy[k];
					if (nx < 0 || ny < 0 || nx >= n || ny >= m ||
						vit[nx][ny] || arr[top.x][top.y] != arr[nx][ny]) continue;
					vit[nx][ny] = true;
					q.push({ nx, ny });
				}
			}
			int sz = vec.size();
			for (auto& p : vec)
				ans[p.x][p.y] = sz;
		}
	}
	for (int i = n/3; i < 2*n/3; i++)
	{
		for (int j = m/3; j < 2*m/3; j++) 
			cout << ans[i][j] << " ";
		cout << "\n";
	}
	return 0;
}

• Subtask 1: 0 / 7