제출 #914932

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914932		SchillingW	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1046 ms	100244 KiB

tracks

#include <iostream>
#include <queue>

int main() {

    int N, M;
    std::cin >> N >> M;
    char g[N * M];
    for (int i = 0; i < N * M; i++) std::cin >> g[i];

    int D[4] {-1, -M, 1, M};

    int d[N * M];
    std::fill(d, d + N * M, -1);
    std::queue<int> q, pq;

    q.push(0);
    d[0] = 1;
    while (!q.empty() || !pq.empty()) {

        int p;
        if (!pq.empty()) p = pq.front(), pq.pop();
        else p = q.front(), q.pop();

        for (int i : D) {
            if (p + i >= 0 && p + i < N * M && !(i == -1 && p % M == 0) && !(i == 1 && p % M == M - 1)) {
                if (g[p + i] != '.' && d[p + i] == -1) {

                    if (g[p] == g[p + i]) pq.push(p + i), d[p + i] = d[p];
                    else q.push(p + i), d[p + i] = d[p] + 1;
                }
            }
        }
    }

    int w = 0;
    for (int i = 0; i < N * M; i++) if (d[i] > w) w = d[i];

    std::cout << w << "\n";
}

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