제출 #1187137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187137		vux2code	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	694 ms	239888 KiB

tracks

// Src : Vux2Code
/* Note :

*/

#include <bits/stdc++.h>
#define fi first
#define se second
#define pusb push_back
#define popb pop_back
#define pusf push_front
#define popf pop_front

using namespace std;

// template <typename T> void vout(T s){ cout << s << endl; exit(0);}

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;

const ll maxN = 4e3 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;

void maxi (ll &x, ll y) {x = max (x, y);}
void mini (ll &x, ll y) {x = min (x, y);}

/* ---------HASHING-------- */
// const base = 31, mod2 = 1e9 + 9;

/* ---------BITMASK-------- */
// ll count (ll x) {return __builtin_popcountll (x);}
// ll fst (ll x) {return 63 - __builtin_clzll (x);}
// ll last (ll x) {return __builtin_ctzll (x);}
// bool bit (ll x, ll y) {return ((x >> y) & 1);}

pll adj [] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

ll t = 1;

ll n, m, d [maxN] [maxN];
char a [maxN] [maxN];
deque <pll> q;

char c (pll x) {
    return a [x. fi] [x. se];
}

bool outBoard (pll x) {
    return x. fi < 1 || x. fi > n || x. se < 1 || x. se > m || a [x. fi] [x. se] == '.';
}

void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> a [i] [j];
        }
    }
    memset (d, 0x3f, sizeof d);
    d [1] [1] = 1;
    q. pusb ({1, 1});
    ll ans = 0;
    while (!q. empty ()) {
        pll tmp = q. front (); 
        // cerr << tmp. fi << ' ' << tmp. se << ' ' << d [tmp. fi] [tmp. se] << '\n';
        maxi (ans, d [tmp. fi] [tmp. se]);
        q. popf ();
        for (pll i : adj) {
            pll nx = {tmp. fi + i. fi, tmp. se + i. se};
            if (outBoard (nx)) continue;
            if (c (nx) == c (tmp)) {
                if (d [nx. fi] [nx. se] > d [tmp. fi] [tmp. se]) {
                    d [nx. fi] [nx. se] = d [tmp. fi] [tmp. se];
                    q. pusf (nx);
                }
            }
            else {
                if (d [nx. fi] [nx. se] > d [tmp. fi] [tmp. se] + 1) {
                    d [nx. fi] [nx. se] =d [tmp. fi] [tmp. se] + 1;
                    q. pusb (nx);
                }
            }
        }
    }
    cout << ans;
}

int main () {
    ios::sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);
    // #define TASK "E:/Code/CP/task"
    // if (fopen (TASK".inp", "r")) {
    //     freopen (TASK".inp", "r", stdin);
    //     freopen (TASK".out", "w", stdout);
    // }
    //cin >> t;
    while (t--) solve ();
}

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