Submission #550091

#	Time	Username	Problem	Language	Result	Execution time	Memory
550091		zxcvbnm	Tracks in the Snow (BOI13_tracks)	C++17	97.81 / 100	905 ms	1048576 KiB

tracks

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

constexpr int nax = 4005;
#define ar array<int, 3>
char mat[nax][nax];
int dep[nax][nax];
int n, m;
int best_so_far[nax][nax];


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

bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

int ans = 0;
//priority_queue<ar, vector<ar>, greater<ar>> q;
queue<ar> q;

void fill(int x, int y, int d) {
    if (dep[x][y] != 0) return;

    dep[x][y] = d;
    ans = max(ans, d);
    for(int i = 0; i < 4; i++) {
        int X = x + dx[i];
        int Y = y + dy[i];
        if (in(X, Y) && dep[X][Y] == 0) {
            if (mat[X][Y] == mat[x][y]) {
                fill(X, Y, d);
            }
            else if (mat[X][Y] != '.') {
                if (d+1 < best_so_far[X][Y]) {
                    best_so_far[X][Y] = d+1;
                    q.push({d+1, X, Y});
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("test.txt", "r", stdin);

    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> mat[i][j];
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            best_so_far[i][j] = nax * nax;
        }
    }

//    assert(mat[0][0] == mat[n-1][m-1]);
    q.push({1, 0, 0});

    while(!q.empty()) {
        ar v = q.front();
        q.pop();

        fill(v[1], v[2], v[0]);
//        break;

//        for(int i = 0; i < n; i++) {
//            for(int j = 0; j < m; j++) {
//                cout << dep[i][j] << " ";
//            }
//            cout << "\n";
//        } cout << "\n";
    }

//    for(int i = 0; i < n; i++) {
//        for(int j = 0; j < m; j++) {
//            cout << dep[i][j] << " ";
//        }
//        cout << "\n";
//    }

    cout << ans << "\n";

    return 0;
}

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