Submission #1324002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324002		sh_qaxxorov_571	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	382 ms	112176 KiB

tracks

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>

using namespace std;

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

int main() {
    // Tezkor kiritish va chiqarish
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int H, W;
    cin >> H >> W;

    vector<string> meadow(H);
    for (int i = 0; i < H; i++) {
        cin >> meadow[i];
    }

    // Masofalarni saqlash uchun massiv (-1 hali ko'rilmagan degani)
    vector<vector<int>> dist(H, vector<int>(W, -1));
    deque<pair<int, int>> dq;

    // Boshlang'ich nuqtani belgilaymiz
    dist[0][0] = 1;
    dq.push_back({0, 0});

    int max_depth = 1;

    while (!dq.empty()) {
        pair<int, int> curr = dq.front();
        dq.pop_front();
        int r = curr.first;
        int c = curr.second;

        max_depth = max(max_depth, dist[r][c]);

        for (int i = 0; i < 4; i++) {
            int nr = r + dx[i];
            int nc = c + dy[i];

            // Maydon ichida ekanligini va qor emasligini tekshiramiz
            if (nr >= 0 && nr < H && nc >= 0 && nc < W && meadow[nr][nc] != '.' && dist[nr][nc] == -1) {
                if (meadow[nr][nc] == meadow[r][c]) {
                    // Bir xil turdagi iz - masofa 0
                    dist[nr][nc] = dist[r][c];
                    dq.push_front({nr, nc});
                } else {
                    // Har xil turdagi iz - masofa 1 (yangi hayvon)
                    dist[nr][nc] = dist[r][c] + 1;
                    dq.push_back({nr, nc});
                }
            }
        }
    }

    cout << max_depth << endl;

    return 0;
}

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