Submission #1249364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249364		starbinhas	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	907 ms	122564 KiB

tracks

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

#define INF 16000001

typedef pair<int, int> pii;

int main() {
    int h, w;
    cin >> h >> w;
    
    char grid[h + 2][w + 2];
    for (int i = 0; i <= h + 1; i++) {
        for (int j = 0; j <= w + 1; j++) {
            if (i < 1 || i > h || j < 1 || j > w) grid[i][j] = '.';
            else cin >> grid[i][j];
        }
    }

    int d[h + 1][w + 1];
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            d[i][j] = INF;
        }
    }
    d[h][w] = 0;
    deque<pii> q;
    q.push_front({h, w});
    bool processed[h + 1][w + 1] = {};
    while (!q.empty()) {
        int a, b;
        tie(a, b) = q.front();
        q.pop_front();
        if (processed[a][b]) continue;
        processed[a][b] = true;
        if (grid[a + 1][b] != '.' && d[a + 1][b] > d[a][b] + (grid[a + 1][b] != grid[a][b])) {
            d[a + 1][b] = d[a][b] + (grid[a + 1][b] != grid[a][b]);
            if (grid[a + 1][b] != grid[a][b]) q.push_back({a + 1, b});
            else q.push_front({a + 1, b});
        }
        if (grid[a - 1][b] != '.' && d[a - 1][b] > d[a][b] + (grid[a - 1][b] != grid[a][b])) {
            d[a - 1][b] = d[a][b] + (grid[a - 1][b] != grid[a][b]);
            if (grid[a - 1][b] != grid[a][b]) q.push_back({a - 1, b});
            else q.push_front({a - 1, b});
        }
        if (grid[a][b + 1] != '.' && d[a][b + 1] > d[a][b] + (grid[a][b + 1] != grid[a][b])) {
            d[a][b + 1] = d[a][b] + (grid[a][b + 1] != grid[a][b]);
            if (grid[a][b + 1] != grid[a][b]) q.push_back({a, b + 1});
            else q.push_front({a, b + 1});
        }
        if (grid[a][b - 1] != '.' && d[a][b - 1] > d[a][b] + (grid[a][b - 1] != grid[a][b])) {
            d[a][b - 1] = d[a][b] + (grid[a][b - 1] != grid[a][b]);
            if (grid[a][b - 1] != grid[a][b]) q.push_back({a, b - 1});
            else q.push_front({a, b - 1});
        }
    }

    int ans = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (grid[i][j] != '.') ans = max(ans, d[i][j]);
        }
    }
    cout << ans + 1 << endl;

    return 0;
}

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