Submission #1050870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050870		inkvizytor	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	455 ms	127756 KiB

tracks

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    vector<string> s (h);
    for (int i = 0; i < h; i++) {
        cin >> s[i];
    }
    deque<pair<pair<short, short>, int>> q;
    vector<vector<bool>> odw (h, vector<bool>(w, 0));
    q.push_back({{0, 0}, 1});
    int maxd = 0;
    while (!q.empty()) {
        auto x = q.front();
        short i = x.first.first, j = x.first.second;
        q.pop_front();
        if (odw[i][j]) {
            continue;
        }
        maxd = max(maxd, x.second);
        odw[i][j] = 1;
        if (i != 0 && !odw[i-1][j] && s[i-1][j] != '.') {
            if (s[i][j] == s[i-1][j]) {
                q.push_front({{i-1, j}, x.second});
            }
            else {
                q.push_back({{i-1, j}, x.second+1});
            }
        }
        if (j != 0 && !odw[i][j-1] && s[i][j-1] != '.') {
            if (s[i][j] == s[i][j-1]) {
                q.push_front({{i, j-1}, x.second});
            }
            else {
                q.push_back({{i, j-1}, x.second+1});
            }
        }
        if (i != h-1 && !odw[i+1][j] && s[i+1][j] != '.') {
            if (s[i][j] == s[i+1][j]) {
                q.push_front({{i+1, j}, x.second});
            }
            else {
                q.push_back({{i+1, j}, x.second+1});
            }
        }
        if (j != w-1 && !odw[i][j+1] && s[i][j+1] != '.') {
            if (s[i][j] == s[i][j+1]) {
                q.push_front({{i, j+1}, x.second});
            }
            else {
                q.push_back({{i, j+1}, x.second+1});
            }
        }

    }
    cout << maxd << '\n';
}

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