Submission #1092579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092579		raczek	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	669 ms	218308 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator <<(auto& o, pair<auto, auto> p) {return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator <<(auto& o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cout<<"["#X"]"<<X<<endl;
#else
#define debug(X) {}
#endif
#define int long long
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin>>n>>m;
	vector brd(n+2, vector(m+2, '.'));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>brd[i][j];
	vector<int> dx = {1, -1, 0, 0};
	vector<int> dy = {0, 0, 1, -1};
	vector dist(n+2, vector(m+2, (int)1e9));
	deque<pair<int, int> > q;
	q.push_back({1, 1});
	dist[1][1] = 1;
	while(!q.empty())
	{
		auto a = q.front();
		q.pop_front();
		for(int i=0;i<4;i++)
		{
			int nx = a.first + dx[i], ny = a.second + dy[i];
			if(brd[nx][ny] == '.') continue;
			int d = 0;
			if(brd[nx][ny] != brd[a.first][a.second]) d = 1;
			if(dist[nx][ny] > dist[a.first][a.second] + d)
			{
				dist[nx][ny] = dist[a.first][a.second]+d;
				if(d == 0) q.push_front({nx, ny});
				if(d == 1) q.push_back({nx, ny});
			}
		}
	}
	debug(dist);
	int res = 1;
	for(auto v : dist)
		for(auto u : v)
			if(u != 1e9) res = max(res, u);
	cout<<res;
}

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