Submission #1089502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089502		Gervid	Zoo (COCI19_zoo)	C++17	110 / 110	79 ms	2908 KiB

zoo

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <limits.h>
#include <algorithm>
#include <math.h>

using namespace std;

struct node
{
	int x, y;
	int layer;

	const bool operator< (const node other) const
	{
		return layer > other.layer;
	}
};

int r, c;

bool outofbounds(node n)
{
	return !(0 <= n.x && n.x < r && 0 <= n.y && n.y < c);
}

int main()
{
	iostream::sync_with_stdio(0);
	cin.tie(0);

	int i, j, deepest_layer = 0;
	cin >> r >> c;

	vector<string> g(r);
	for (i = 0; i < r; i++)
	{
		cin >> g[i];
	}

	priority_queue<node> q;
	q.push({ 0, 0, 0 });

	vector<vector<bool>> been(r, vector<bool>(c, 0));
	vector<pair<int, int>> directions = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

	while (!q.empty())
	{
		node current = q.top();
		q.pop();

		for (pair<int, int>& d : directions)
		{
			node neighbour;
			neighbour.x = current.x + d.first;
			neighbour.y = current.y + d.second;

			if (!outofbounds(neighbour) && !been[neighbour.x][neighbour.y] && g[neighbour.x][neighbour.y] != '*')
			{
				neighbour.layer = current.layer + (g[neighbour.x][neighbour.y] != g[current.x][current.y]);
				deepest_layer = max(deepest_layer, neighbour.layer);

				q.push(neighbour);
				been[neighbour.x][neighbour.y] = true;
			}
		}
	}

	cout << deepest_layer + 1;
}

Compilation message (stderr)

zoo.cpp: In function 'int main()':
zoo.cpp:36:9: warning: unused variable 'j' [-Wunused-variable]
   36 |  int i, j, deepest_layer = 0;
      |         ^

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