Submission #571317

#	Time	Username	Problem	Language	Result	Execution time	Memory
571317		_karan_gandhi	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1678 ms	398124 KiB

tracks

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

#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long

void solve() {
	int n, m; cin >> n >> m;

	vector<string> arr(n);

	for (int i = 0; i < n; i++) cin >> arr[i];

	deque<pair<pair<int, int>, int>> dq;
	int ans = 0;
	dq.emplace_back(make_pair(0, 0), 0);
	vector<vector<bool>> vis(n, vector<bool>(m, 0));
	
	int dx[] = {0, 0, 1, -1};
	int dy[] = {1, -1, 0, 0};

	auto is_within_bounds = [&](int x, int y) {
		return x >= 0 && x < n && y >= 0 && y < m;
	};

	while (dq.size() != 0) {
		auto [node, dist] = dq.front();
		dq.pop_front();

		if (vis[node.first][node.second]) continue;
		vis[node.first][node.second] = 1;

		ans = max(ans, dist);
		
		int x = node.first;
		int y = node.second;
		
		for (int i = 0; i < 4; i++) {
		
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (is_within_bounds(nx, ny)) {

				if (arr[nx][ny] == '.') continue;
				if (arr[nx][ny] == arr[x][y]) {
					dq.emplace_front(make_pair(nx, ny), dist);
				} else {
					dq.emplace_back(make_pair(nx, ny), dist + 1);
				}
			}
		}
	}

	cout << ans + 1 << endl;
}

int main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
	// cin >> T;
	while (T--)
		solve();
}

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