Submission #1303352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303352		SzymonKrzywda	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	583 ms	119256 KiB

tracks

#include <iostream>
#include <queue>

using namespace std;


const int MAXN = 4000 + 7;
char tab[MAXN][MAXN];
int ans[MAXN][MAXN];

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); 

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tab[i][j];
            ans[i][j] = 1e9;
        }
    }


    deque<pair<int, int>> kolejka;
    ans[0][0] = 1;
    kolejka.push_back({0, 0});

    while (!kolejka.empty()) {
        int x = kolejka.front().first;
        int y = kolejka.front().second;
        kolejka.pop_front();

        for (int i = 0; i < 4; i++) {
            int new_x = x + dx[i];
            int new_y = y + dy[i];
            if (new_x >= n || new_x < 0 || new_y < 0 || new_y >= m) continue;
            if (tab[new_x][new_y] == '.') continue;
            else if (tab[new_x][new_y] != tab[x][y] && ans[new_x][new_y] > ans[x][y] + 1) {
                ans[new_x][new_y] = ans[x][y] + 1;
                kolejka.push_back({new_x, new_y});
            } 
            else if( tab[new_x][new_y] == tab[x][y] && ans[new_x][new_y] > ans[x][y]) {
                ans[new_x][new_y] = ans[x][y];
                kolejka.push_front({new_x, new_y});
            }
        }
    }


    int maxi = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ans[i][j] != 1e9) maxi = max(maxi, ans[i][j]);
        }
    }

    cout << maxi << '\n';

    return 0;
}

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