Submission #523345

#	Time	Username	Problem	Language	Result	Execution time	Memory
523345		blue	Zoo (COCI19_zoo)	C++17	110 / 110	120 ms	6104 KiB

zoo

#include <iostream>
#include <string>
#include <deque>
#include <vector>
using namespace std;

using vi = vector<int>;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int R, C;
	cin >> R >> C;

	char S[R*C];
	for(int i = 0; i < R*C; i++) cin >> S[i];

	int res = 1;

	vi dist(R*C, R*C*5);
	dist[0] = 0;

	deque<int> tbv;

	tbv.push_back(0);

	while(!tbv.empty())
	{
		int u = tbv.front();
		tbv.pop_front();

		res = max(res, dist[u] + 1);

		vi edge;
		if(u % C != 0) edge.push_back(u-1);
		if(u % C != C-1) edge.push_back(u+1);
		if(u / C != 0) edge.push_back(u-C);
		if(u / C != R-1) edge.push_back(u+C);

		for(int v : edge)
		{
			int d = (S[u] != S[v]);

			if(S[v] == '*') continue;

			if(dist[v] <= dist[u] + d) continue;

			dist[v] = dist[u] + d;

			if(d == 0) tbv.push_front(v);
			else tbv.push_back(v);
		}
	}

	cout << res << '\n';
}

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