제출 #1284921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284921		swusjask	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	749 ms	208960 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vpl = vector<pll>;

#define pb push_back
#define fi first
#define se second
#define f(i, a, b) for (ll i = a; i <= b; i++)
#define fr(i, a, b) for (ll i = b; i >= a; i--)
#define sz(x) (ll) x.size()
#define debug(val) cerr << #val << " = " << val << '\n';
#define all(x) x.begin(), x.end()

const ll MOD = 1e9 + 7;

void bfs(ll start, vector<vl> &adj, vector<pll> &path) {
    path[start] = {-1,1};
    queue<ll> q;
    q.push(start);

    while (!q.empty()) {
        ll u = q.front(); q.pop();
        ll ct = path[u].se;
        for (ll v: adj[u]) {
            if (path[v] != pll{-1,-1}) continue;
            path[v] = {u,ct+1};
            q.push(v);
        }
    }
}

const vl H_CHANGE = {0,1,0,-1};
const vl W_CHANGE = {1,0,-1,0};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // string name = "time";
    // freopen((name + ".in").c_str(), "r", stdin);
    // freopen((name + ".out").c_str(), "w", stdout);

    // precompute
    // vl dices = {1,2,3,4,5,6};

    ll h,w;
    cin >> h >> w;
    vector<vc> grid(h, vc(w));

    f(i,0,h-1) f(ii,0,w-1) cin >> grid[i][ii];

    vector<vl> d(h, vl(w, LLONG_MAX));
    d[0][0] = 1;
    deque<pll> q;
    q.push_front({0,0});
    ll ans = 1;

    while (!q.empty()) {
        auto [uh,uw] = q.front();
        q.pop_front();
        ans = max(ans, d[uh][uw]);
        // debug(uh);debug(uw);

        f(i,0,3) {
            ll vh = uh + H_CHANGE[i];
            ll vw = uw + W_CHANGE[i];
            

            if (vh < 0 || vw < 0 || vh == h || vw == w || grid[vh][vw] == '.') continue;

            ll cost = grid[uh][uw] != grid[vh][vw];
            if (d[uh][uw] + cost < d[vh][vw]) {
                d[vh][vw] = d[uh][uw] + cost;
                // debug(vh);debug(vw);debug(d[vh][vw]);
                if (cost == 1) q.push_back({vh,vw});
                else q.push_front({vh,vw});
            }
        }
    }

    cout << ans << "\n";
}

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