Submission #1296296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296296		__ugur__	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	450 ms	122560 KiB

tracks

#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;
using u64 = uint64_t;
using u32 = uint32_t;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int h,w;
	cin >> h >> w;
	vector<vector<int>> depths(h, vector<int>(w, -1));
	vector<string> meadow(h);
	for(auto& str : meadow)
		cin >> str;

	deque<pair<int, int>> qu;
	
	int ans = 0;

	const int xoff[4] = {-1, 0, 0, 1};
	const int yoff[4] = {0, -1, 1, 0};

	depths[0][0] = 1;
	qu.push_back({0, 0});

	while(qu.size()) {
		auto [y, x] = qu.front();
		qu.pop_front();
		ans = max(ans, depths[y][x]);
		for(int cy,cx,i=0; i<4; i++) {
			cy = y + yoff[i];
			cx = x + xoff[i];
			if(cy < 0 || cx < 0 || cy >= h || cx >= w || depths[cy][cx] >= 0 || meadow[cy][cx] == '.')
				continue;
			if(meadow[y][x] == meadow[cy][cx]) {
				qu.push_front({cy, cx});
				depths[cy][cx] = depths[y][x];
			}
			else {
				qu.push_back({cy, cx});
				depths[cy][cx] = depths[y][x]+1;
			}
		}
	}

	cout << ans << '\n';

	return 0;
}

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