Submission #1037028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037028		ArthuroWich	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	458 ms	212700 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long int
void solve() {
    int n, m, ans = 0;
    cin >> n >> m;
    vector<string> grid(n);
    vector<vector<int>> dist(n, vector<int>(m, 0)); 
    for (string &x : grid) {
        cin >> x;
    }
    deque<pair<int, int>> q;
    dist[0][0] = 1;
    q.push_back({0, 0});
    while(!q.empty()) {
        auto [i, j] = q.front();
        q.pop_front();
        if (i+1 < n && !dist[i+1][j] && grid[i+1][j] != '.') {
            dist[i+1][j] = dist[i][j];
            if (grid[i][j] != grid[i+1][j]) {
                dist[i+1][j]++;
                q.push_back({i+1, j});
            } else {
                q.push_front({i+1, j});
            }
        }
        if (j+1 < m && !dist[i][j+1] && grid[i][j+1] != '.') {
            dist[i][j+1] = dist[i][j];
            if (grid[i][j] != grid[i][j+1]) {
                dist[i][j+1]++;
                q.push_back({i, j+1});
            } else {
                q.push_front({i, j+1});
            }
        }
        if (i-1 >= 0 && !dist[i-1][j] && grid[i-1][j] != '.') {
            dist[i-1][j] = dist[i][j];
            if (grid[i][j] != grid[i-1][j]) {
                dist[i-1][j]++;
                q.push_back({i-1, j});
            } else {
                q.push_front({i-1, j});
            }
        }
        if (j-1 >= 0 && !dist[i][j-1] && grid[i][j-1] != '.') {
            dist[i][j-1] = dist[i][j];
            if (grid[i][j] != grid[i][j-1]) {
                dist[i][j-1]++;
                q.push_back({i, j-1});
            } else {
                q.push_front({i, j-1});
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans = max(ans, dist[i][j]);
        }
    }
    cout << ans << endl;
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

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