Submission #251642

#	Time	Username	Problem	Language	Result	Execution time	Memory
251642		MrRobot_28	Zoo (COCI19_zoo)	C++17	110 / 110	53 ms	2560 KiB

zoo

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

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	vector <vector <char> > a(n, vector <char> (m));
	vector <vector <bool> > used(n, vector <bool> (m));
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> a[i][j];
		}
	}
	queue <pair <int, int> > q1, q2;
	used[0][0] = true;
	if(a[0][0] == 'T')
	{
		q1.push({0, 0});
	}
	else if(a[0][0] == 'B')
	{
		q2.push({0, 0});
	}
	int cnt = 0;
	while(q1.size() > 0 || q2.size() > 0)
	{
		if(q1.size() > 0)
		{
			cnt++;
		}
		while(q1.size() > 0)
		{
			pair <int, int> v = q1.front();
			q1.pop();
			int x = v.first;
			int y = v.second;
			if(x > 0 && !used[x - 1][y])
			{
				used[x - 1][y] = true;
				if(a[x - 1][y] == 'T')
				{
					q1.push({x - 1, y});
				}
				else if(a[x - 1][y] == 'B')
				{
					q2.push({x - 1, y});
				}
			}
			if(x < n - 1 && !used[x + 1][y])
			{
				used[x + 1][y] = true;
				if(a[x + 1][y] == 'T')
				{
					q1.push({x + 1, y});
				}
				else if(a[x + 1][y] == 'B')
				{
					q2.push({x + 1, y});
				}
			}
			if(y > 0 && !used[x][y - 1])
			{
				used[x][y - 1] = true;
				if(a[x][y - 1] == 'T')
				{
					q1.push({x, y - 1});
				}
				else if(a[x][y - 1] == 'B')
				{
					q2.push({x, y - 1});
				}
			}
			if(y < m - 1 && !used[x][y + 1])
			{
				used[x][y + 1] = true;
				if(a[x][y + 1] == 'T')
				{
					q1.push({x, y + 1});
				}
				else if(a[x][y + 1] == 'B')
				{
					q2.push({x, y + 1});
				}
			}
		}
		if(q2.size() > 0)
		{
			cnt++;
		}
		while(q2.size() > 0)
		{
			pair <int, int> v = q2.front();
			q2.pop();
			int x = v.first;
			int y = v.second;
			if(x > 0 && !used[x - 1][y])
			{
				used[x - 1][y] = true;
				if(a[x - 1][y] == 'T')
				{
					q1.push({x - 1, y});
				}
				else if(a[x - 1][y] == 'B')
				{
					q2.push({x - 1, y});
				}
			}
			if(x < n - 1 && !used[x + 1][y])
			{
				used[x + 1][y] = true;
				if(a[x + 1][y] == 'T')
				{
					q1.push({x + 1, y});
				}
				else if(a[x + 1][y] == 'B')
				{
					q2.push({x + 1, y});
				}
			}
			if(y > 0 && !used[x][y - 1])
			{
				used[x][y - 1] = true;
				if(a[x][y - 1] == 'T')
				{
					q1.push({x, y - 1});
				}
				else if(a[x][y - 1] == 'B')
				{
					q2.push({x, y - 1});
				}
			}
			if(y < m - 1 && !used[x][y + 1])
			{
				used[x][y + 1] = true;
				if(a[x][y + 1] == 'T')
				{
					q1.push({x, y + 1});
				}
				else if(a[x][y + 1] == 'B')
				{
					q2.push({x, y + 1});
				}
			}
		}
	}
	cout << cnt;
  	return 0;
}

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65