Submission #1265049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265049		canhnam357	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	548 ms	112120 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (string &s : a) cin >> s;
    vector<vector<int>> d(n, vector<int>(m, INT_MAX));
    deque<pair<int, int>> dq;
    dq.emplace_front(0, 0);
    d[0][0] = 1;
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    while (!dq.empty()) {
        auto [x, y] = dq.front();
        dq.pop_front();
        for (int k = 0; k < 4; k++) {
            int r = x + dx[k], c = y + dy[k];
            if (min({r, c, n - r - 1, m - c - 1}) >= 0) {
                if (a[r][c] == '.') continue;
                if (a[r][c] == a[x][y]) {
                    int nd = d[x][y];
                    if (nd < d[r][c]) {
                        d[r][c] = nd;
                        dq.emplace_front(r, c);
                    }
                }
                else {
                    int nd = d[x][y] + 1;
                    if (nd < d[r][c]) {
                        d[r][c] = nd;
                        dq.emplace_back(r, c);
                    }
                }
            }
        }
    }   
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] != '.') ans = max(ans, d[i][j]);
        }
    }
    cout << ans;
    return 0;
}

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