Submission #1207151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207151		andrejikus	Tracks in the Snow (BOI13_tracks)	C++20	84.69 / 100	2097 ms	64744 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)

const int N = 4003;
char a[N][N];
bool vis[N][N];
const int POM[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void solve() {
    int n, m; cin >> n >> m;
    priority_queue<tuple<int, int, int, char>, vector<tuple<int, int, int, char>>, greater<>> pq;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];

    pq.emplace(1, n, m, a[n][m]);
    int ans = 1;

    while (!pq.empty()) {
        auto [w, i, j, c] = pq.top(); pq.pop();
        if (vis[i][j]) continue;
        ans = max(ans, w);
        vis[i][j] = true;
        for (int d = 0; d < 4; d++) {
            int ik = i + POM[d][0], jk = j + POM[d][1];
            if (ik < 1 || ik > n || jk < 1 || jk > m) continue;
            if (vis[ik][jk] || a[ik][jk] == '.') continue;
            char c2 = a[ik][jk];
            pq.emplace(w + (c != c2), ik, jk, c2);
        }
    }

    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
	int t=1; //cin >> t;
	while (t--) {
        solve();
	}
}

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