Submission #456372

#	Time	Username	Problem	Language	Result	Execution time	Memory
456372		Jasiekstrz	Zoo (COCI19_zoo)	C++17	110 / 110	71 ms	7116 KiB

zoo

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e3;
vector<pair<int,int>> moves={{-1,0},{1,0},{0,-1},{0,1}};
char t[N+10][N+10];
int d[N+10][N+10];
queue<pair<int,pair<int,int>>> qq[2];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>t[i][j];
			d[i][j]=N*N+10;
			if(t[i][j]=='*')
				d[i][j]=-1;
		}
	}
	qq[0].push({0,{1,1}});
	while(true)
	{
		int dx;
		pair<int,int> x;
		if(!qq[0].empty())
		{
			dx=qq[0].front().fi;
			x=qq[0].front().se;
			qq[0].pop();
		}
		else if(!qq[1].empty())
		{
			dx=qq[1].front().fi;
			x=qq[1].front().se;
			qq[1].pop();
		}
		else
			break;
		if(d[x.fi][x.se]<=dx)
			continue;
		d[x.fi][x.se]=dx;
		for(auto v:moves)
		{
			v.fi+=x.fi;
			v.se+=x.se;
			if(v.fi<1 || n<v.fi || v.se<1 || m<v.se)
				continue;
			if(t[x.fi][x.se]!=t[v.fi][v.se])
				qq[1].emplace(dx+1,v);
			else
				qq[0].emplace(dx,v);
		}
	}
	int mx=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			mx=max(mx,d[i][j]+1);
	}
	cout<<mx<<"\n";
	return 0;
}

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