Submission #1233244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233244		thaocherry	Tracks in the Snow (BOI13_tracks)	C++20	82.50 / 100	2098 ms	88372 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll H, W;
vector<ll> X{0,0,1,-1}, Y{1,-1,0,0};
const ll lim = 4e3 + 10;
char g[lim][lim], check[lim][lim];
struct abc{
    ll d,x,y;
};
bool cmp(abc a, abc b)
{
    if(a.d != b.d) return a.d < b.d;
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
set<abc, decltype(&cmp)> s(&cmp);
void init()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
}
void dj()
{
    ll ans = 1;
    s.insert({1,1,1});

    for(;s.size();)
    {
        abc t = *s.begin();
        s.erase(s.begin());
        ans = max(ans, t.d);
        if(check[t.x][t.y]) continue;
        check[t.x][t.y] = 1;
        for(ll i = 0; i < 4; i++)
        {
            ll vtX = t.x + X[i];
            ll vtY = t.y + Y[i];
            if(vtX <= 0 || vtX > H || vtY <= 0 || vtY > W || g[vtX][vtY] == '.' || check[vtX][vtY]) continue;
            if(g[vtX][vtY] != g[t.x][t.y]) s.insert({t.d + 1, vtX, vtY});
            else s.insert({t.d, vtX, vtY});
        }
    }
    cout << ans;
}
int main()
{
    init();
    cin >> H >> W;
    for(ll i = 1; i <= H; i++)
        for(ll j = 1; j <= W; j++) cin >> g[i][j];
    dj();

}

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