Submission #629746

#	Time	Username	Problem	Language	Result	Execution time	Memory
629746		diponkinu	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	590 ms	251544 KiB

tracks

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

int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
vector<string> snow(4000);
vector<vector<int>> depth(4000,vector<int>(4000)); 
int n,m,ans=1;
bool inside(int x, int y)
{
	if(-1<x&&x<n&&-1<y&&y<m&&snow[x][y]!='.')
	{
		return true;
	}
	return false;
}
signed main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i=0;i<n;i++)
	{
		cin >> snow[i];
	}
	depth[0][0]=1;
	deque<pair<int,int>> q;
	q.push_back({0,0});
	while(q.size())
	{
		pair<int,int> now = q.front();
		q.pop_front();
		ans = max(ans,depth[now.first][now.second]);
		for(int i=0;i<4;i++)
		{
			int x=now.first + dx[i],y=now.second + dy[i];
			if(inside(x,y)&&depth[x][y]==0)
			{
				if(snow[x][y]==snow[now.first][now.second])
				{
					depth[x][y]=depth[now.first][now.second];
					q.push_front({x,y});
				}
				else
				{
					depth[x][y]=depth[now.first][now.second]+1;
					q.push_back({x,y});
				}
			}
		}
	}
	cout<<ans;

}

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