Submission #444365

#	Time	Username	Problem	Language	Result	Execution time	Memory
444365		mhsi2005	Tracks in the Snow (BOI13_tracks)	C++17	67.71 / 100	2098 ms	165060 KiB

tracks

#include<bits/stdc++.h>
using namespace std;

const long long maxn = 4000 + 10, INF = 1e9 + 10;

long long n, m, h, w;
bool vis[maxn];
char meadow[maxn][maxn];

int main() {
    cin >> h >> w;
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            cin >> meadow[i][j];
    long long adj[4]{1, -1, w, -w};
    vector<long long> d(maxn * maxn, INF);
    d[1] = 0;
    deque<int> q;
    q.push_back(1);
    while (q.size()) {
        int v = q.front();
        q.pop_front();
        for (int a : adj) {
            int u = a + v;
            int i = (v-1) / w + 1, j = v % w,
                x = (u-1) / w + 1, y = u % w;
            if (x <= 0 || y <= 0) continue;
            if (x > h || y > w) continue;
            if (meadow[x][y] == '.') continue;
            int w = !(meadow[i][j] == meadow[x][y]);
            if (d[v] + w < d[u]) {
                d[u] = d[v] + w;
                if (w == 1)
                    q.push_back(u);
                else
                    q.push_front(u);
            }
        }
    }
    long long mx = 0;
    for (int i = 1; i <= w * h; i++) {
        if (d[i] < INF)
            mx = max(mx, d[i]);
    }
    cout << mx + 1 << '\n';
    return 0;
}

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