Submission #1107604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107604		danielsuh	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	434 ms	123152 KiB

tracks

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int N, M; cin >> N >> M;
	vector<string> grid(N); for(auto &x : grid) cin >> x;
	vector<vector<int>> depth(N, vector<int>(M, 0));

	depth[0][0] = 1;
	deque<pair<int, int>> dq;
	dq.push_back({0, 0});

	int mx = 1;

	while(!dq.empty()) {
		pair<int, int> cur = dq.front(); dq.pop_front();
		mx = max(mx, depth[cur.first][cur.second]);
		for(int i = 0; i < 4; i++) {
			pair<int, int> next = {cur.first + dx[i], cur.second + dy[i]};
			if(next.first < 0 || next.first >= N || next.second < 0 || next.second >= M) continue;
			if(depth[next.first][next.second] == 0 && grid[next.first][next.second] != '.') {
				if(grid[cur.first][cur.second] == grid[next.first][next.second]) {
					depth[next.first][next.second] = depth[cur.first][cur.second];
					dq.push_front({next.first, next.second});
				} else {
					depth[next.first][next.second] = depth[cur.first][cur.second] + 1;
					dq.push_back({next.first, next.second});
				}
			}
		}
	}
	cout << mx << endl;
}

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