Submission #1251319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251319		fulminata	Tracks in the Snow (BOI13_tracks)	C++20	17.60 / 100	1269 ms	1114112 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
template<typename T>
using v = vector<T>;
template<typename T, typename U>
using p = pair<T, U>;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()

ll n, m;
v<v<char>> grid;
v<v<ll>> num;
queue<p<ll, ll>> processing;

void dfs(ll row, ll col) {
    if (row > 0 && grid[row][col] == grid[row - 1][col] && num[row - 1][col] == 1e18) {
        processing.push({row - 1, col});
        num[row - 1][col] = num[row][col];
        dfs(row - 1, col);
    }
    if (row < n - 1 && grid[row][col] == grid[row + 1][col] && num[row + 1][col] == 1e18) {
        processing.push({row + 1, col});
        num[row + 1][col] = num[row][col];
        dfs(row + 1, col);
    }
    if (col > 0 && grid[row][col] == grid[row][col - 1] && num[row][col - 1] == 1e18) {
        processing.push({row, col - 1});
        num[row][col - 1] = num[row][col];
        dfs(row, col - 1);
    }
    if (col < m - 1 && grid[row][col] == grid[row][col + 1] && num[row][col + 1] == 1e18) {
        processing.push({row, col + 1});
        num[row][col + 1] = num[row][col];
        dfs(row, col + 1);
    }
}

void solve() {

    cin >> n >> m;
    grid = v<v<char>>(n, v<char>(m));
    rep(i, 0, n) {
        string s;
        cin >> s;
        rep(j, 0, m) {
            grid[i][j] = s[j];
        }
    }

    num = v<v<ll>>(n, v<ll>(m, 1e18));
    num[0][0] = 1;
    processing.push({0, 0});
    dfs(0, 0);
    while (!processing.empty()) {
        p<ll, ll> fr = processing.front();
        processing.pop();
        ll row = fr.first; ll col = fr.second;

        if (row > 0 && grid[row][col] != grid[row - 1][col] && grid[row - 1][col] != '.' && num[row - 1][col] == 1e18) {
            num[row - 1][col] = num[row][col] + 1;
            dfs(row - 1, col);
        }
        if (row < n - 1 && grid[row][col] != grid[row + 1][col] && grid[row + 1][col] != '.' && num[row + 1][col] == 1e18) {
            num[row + 1][col] = num[row][col] + 1;
            dfs(row + 1, col);
        }
        if (col > 0 && grid[row][col] != grid[row][col - 1] && grid[row][col - 1] != '.' && num[row][col - 1] == 1e18) {
            num[row][col - 1] = num[row][col] + 1;
            dfs(row, col - 1);
        }
        if (col < m - 1 && grid[row][col] != grid[row][col + 1] && grid[row][col + 1] != '.' && num[row][col + 1] == 1e18) {
            num[row][col + 1] = num[row][col] + 1;
            dfs(row, col + 1);
        }
    }
    ll mx = 0;
    rep(i, 0, n) {
        rep(j, 0, m) {
            //if (num[i][j] != 1e18) cout << num[i][j] << " ";
            //else cout << "inf ";
            if (num[i][j] != 1e18) mx = max(mx, num[i][j]);
        } //cout << endl;
    }
    cout << mx << endl;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t = 1;
    //cin >> t;
    while (t-- > 0)
        solve();

}

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