Submission #497260

#	Time	Username	Problem	Language	Result	Execution time	Memory
497260		ljuba	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1428 ms	123564 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

const int mxN = 4002;
char mat[mxN][mxN];
int dist[mxN][mxN];

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

const int INF = 1e9 + 12;

int main() {
    int h, w;
    cin >> h >> w;

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> mat[i][j];
            dist[i][j] = INF;
        }
    }

    deque<pair<int, int>> q;
    q.push_front({h-1, w-1});
    dist[h-1][w-1] = 1;

    auto check = [&](int x, int y) {
        return x >= 0 && x < h && y >= 0 && y < w;
    };

    while(!q.empty()) {
        auto tren = q.front();
        q.pop_front();

        for(int i = 0; i < 4; ++i) {
            if(!check(tren.first+dx[i], tren.second+dy[i])) continue;
            int nx = tren.first+dx[i];
            int ny = tren.second+dy[i];
            if(mat[nx][ny] == '.') continue;
            if(dist[nx][ny] != INF) continue;
            if(mat[nx][ny] != mat[tren.first][tren.second]) {
                dist[nx][ny] = dist[tren.first][tren.second] + 1;
                q.push_back({nx, ny});
            } else {
                dist[nx][ny] = dist[tren.first][tren.second];
                q.push_front({nx, ny});
            }
        }
    }

    int ans = 0;

    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            if(dist[i][j] == INF) continue;
            ans = max(ans, dist[i][j]);
        }
    }

    cout << ans << '\n';
}

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