Submission #1084780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084780		Kiet07	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	505 ms	134872 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
char a[4005][4005];
int dist[4005][4005],dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//freopen("TEST.inp","r",stdin);
	int n,m; cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	dist[1][1]=1;
	deque<pair<int,int>>q;
	int ans=1;
	q.push_back({1,1});
	while(!q.empty())
	{
		pair<int,int>x=q.front(); q.pop_front();
		//cout<<x.first<<' '<<x.second<<' '<<dist[x.first][x.second]<<'\n';
		ans=max(ans,dist[x.first][x.second]);
		for(int k=0;k<4;k++)
		{
			int nx=x.first+dx[k],ny=x.second+dy[k];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&dist[nx][ny]==0&&a[nx][ny]!='.')
			{
				if(a[x.first][x.second]==a[nx][ny])
				{
					dist[nx][ny]=dist[x.first][x.second];
					q.push_front({nx,ny});
				}
				else
				{
					dist[nx][ny]=dist[x.first][x.second]+1;
					q.push_back({nx,ny});
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70