Submission #814300

#	Time	Username	Problem	Language	Result	Execution time	Memory
814300		asdasdqwer	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	957 ms	257620 KiB

tracks

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

#define int int64_t
#define pii pair<int, int>

vector<pii> dir = {{0, 1}, {-1, 0}, {1, 0}, {0, -1}};
int n, m;

pii operator+(const pii &x, const pii &y) {
    return {x.first + y.first, x.second + y.second};
}

bool check(const pii &x) {
    return x.first >= 0 && x.first < n && x.second >= 0 && x.second < m;
}

signed main() {
    cin>>n>>m;
    vector<string> a(n);
    for (auto &x:a)cin>>x;
    vector<vector<int>> d(n, vector<int>(m, 1e9));
    deque<pii> dq;
    dq.push_front({0, 0});
    d[0][0]=1;
    int mx = 0;
    while (!dq.empty()) {
        pii t = dq.front();dq.pop_front();
        mx = max(mx, d[t.first][t.second]);
        // test all dir
        for (pii x:dir) {
            pii temp = t + x;
            if (check(temp) && a[temp.first][temp.second] != '.') {
                int w = (a[t.first][t.second] != a[temp.first][temp.second]);
                if (d[t.first][t.second] + w < d[temp.first][temp.second]) {
                    if (w == 0) {
                        dq.push_front(temp);
                    }

                    else {
                        dq.push_back(temp);
                    }
                    d[temp.first][temp.second]=d[t.first][t.second]+w;
                }
            }
        }
    }

    cout << mx << "\n";
}

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