제출 #1243101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243101		mirbek01	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	632 ms	210040 KiB

tracks

#include <bits/stdc++.h>

#define int long long

using namespace std;

int X[] = {-1, 1, 0, 0};
int Y[] = {0, 0, 1, -1};

signed main() {
//    freopen("cruise.in", "r", stdin);
//    freopen("cruise.out", "w", stdout);
    int n, m;
    cin >> n >> m;

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

    deque < pair <int, int> > q;
    q.push_back({0, 0});
    vector < vector <int> > dist(n, vector <int>(m));
    dist[0][0] = 1; 

    int ans = 1;
    while (!q.empty()) {
        int vx = q.front().first;
        int vy = q.front().second;
        q.pop_front();
        ans = max(ans, dist[vx][vy]);
        for (int i = 0; i < 4; i++) {
            int tox = vx + X[i];
            int toy = vy + Y[i];
            if (tox < 0 || tox >= n || toy < 0 || toy >= m || c[tox][toy] == '.') continue;
            if (!dist[tox][toy]) {
                if (c[vx][vy] == c[tox][toy]) {
                    q.push_front({tox, toy});
                    dist[tox][toy] = dist[vx][vy];
                } else {
                    q.push_back({tox, toy});
                    dist[tox][toy] = dist[vx][vy] + 1;
                }
            }
        }
    }

    cout << ans << endl;
}

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