Submission #1276904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276904		roadster	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	404 ms	111988 KiB

tracks

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

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i, n) for (int i = 0; i < n; i++)
#define reprng(i, a, b) for (int i = (a); i < (b); i++)
#define MOD 1000000007

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;

void setIO(const string &name = "") {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

int dr[] { 0, 1, 0, -1 };
int dc[] { 1, 0, -1, 0 };

int main() {

    setIO();

    int h, w;
    cin >> h >> w;
    vector<string> snow(h);
    rep (i, h) cin >> snow[i];

    vvi depth(h, vi(w));
    deque<pii> dq;
    dq.pb({0, 0});
    depth[0][0] = 1;
    int res = 0;

    while (!dq.empty()) {
        auto curr = dq.front();
        dq.pop_front();
        res = max(res, depth[curr.f][curr.s]);

        for (int i = 0; i < 4; i++) {
            int nxr = curr.f + dr[i];
            int nxc = curr.s + dc[i];

            // cout << nxr << " " << nxc << " ";
            // cout << (!(nxr >= 0 && nxr < h && nxc >= 0 && nxc < w)) << " ";
            if (!(nxr >= 0 && nxr < h && nxc >= 0 && nxc < w && snow[nxr][nxc] != '.')) continue;
            // cout << depth[nxr][nxc] << "\n";
            if (depth[nxr][nxc]) continue;

            // cout << "coming down\n";
            if (snow[nxr][nxc] == snow[curr.f][curr.s]) {
                depth[nxr][nxc] = depth[curr.f][curr.s];
                dq.push_front({nxr, nxc});
            } else {
                depth[nxr][nxc] = depth[curr.f][curr.s] + 1;
                dq.push_back({nxr, nxc});
            }
            // cout << nxr << " " << nxc << " " << depth[nxr][nxc] << "\n";
        }
    }

    // for (int i = 0; i < h; i++) {
    //     for (int j = 0; j < w; j++) cout << depth[i][j] << " ";
    //     cout << "\n";
    // }

    cout << res << "\n";

    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void setIO(const std::string&)':
tracks.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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