Submission #1266876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266876		goppamach	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	531 ms	127236 KiB

tracks

// #pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

#define el "\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define sqr(x) ((x) * (x))
#define FOR(i, l, r) for (int i = l; i <= (r); i++)
#define FOD(i, l, r) for (int i = l; i >= (r); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);

using db = long double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vbool = vector<bool>;
using vvbool = vector<vbool>;

template<class T> inline bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); }
template<class T> inline bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); }

// #define DEBUG
#ifdef DEBUG
#include "D:\cpp\debug.h"
#else
#define debug(...)
#define debug_arr(...)
#endif

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 4E3 + 5;
constexpr int INF = 1E9 + 7;
constexpr ll INFLL = 4E18;
constexpr int MOD = 1E9 + 7; // 998244353
constexpr double EPS = 1E-10;

int H, W;
char grid[N][N];
int d[N][N];

constexpr int DIRECTIONS[4][2] = {{-1, 0}, {+1, 0}, {0, -1}, {0, +1}};

void solve() {
    cin >> H >> W;

    FOR(i, 1, H) {
        FOR(j, 1, W) {
            cin >> grid[i][j];
        }
    }

    if (grid[1][1] == '.') {
        cout << 0 << el;
        return;
    }

    deque<pii> dq;
    memset(d, 0x3f, sizeof d);
    dq.emplace_front(1, 1);
    d[1][1] = 1;
    int res = 1;
    while (!dq.empty()) {
        auto [x, y] = dq.front();
        chmax(res, d[x][y]);
        dq.pop_front();
        for (auto &[dx, dy] : DIRECTIONS) {
            int nx = x + dx, ny = y + dy;
            if (nx < 1 || nx > H || ny < 1 || ny > W || grid[nx][ny] == '.') continue;
            if (grid[nx][ny] == grid[x][y] && chmin(d[nx][ny], d[x][y])) {
                dq.emplace_front(nx, ny);
            }
            if (grid[nx][ny] != grid[x][y] && chmin(d[nx][ny], d[x][y] + 1)) {
                dq.emplace_back(nx, ny);
            }
        }
    }

    cout << res << el;
}

int main() {
    fast_io
    #define LOCAL
    #ifndef LOCAL
    #define PROBLEM "tracks"
    freopen(PROBLEM ".in", "r", stdin);
    freopen(PROBLEM ".out", "w", stdout);
    #endif

    int t = 1;
    // cin >> t;
    while (t--) solve();
}

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