제출 #1161160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161160		intricacies	Tracks in the Snow (BOI13_tracks)	C++20	86.88 / 100	428 ms	163972 KiB

tracks

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main() {
    fast();

    // freopen("haybales.in", "r", stdin);
    // freopen("haybales.out", "w", stdout);

    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    vector<vector<int>> dist(n, vector<int>(m, 1));
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<pii> mv = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    deque<pii> bfs;
    visited[0][0] = true;
    bfs.push_back({0, 0});
    pii cur;
    while (bfs.size()) {
        cur = bfs.front();
        bfs.pop_front();
        for (int i = 0; i < mv.size(); i++)
            if ((cur.first + mv[i].first >= 0) &&
                (cur.first + mv[i].first < n) &&
                (cur.second + mv[i].second >= 0) &&
                (cur.second + mv[i].second < m) &&
                !visited[cur.first + mv[i].first][cur.second + mv[i].second] &&
                a[cur.first + mv[i].first][cur.second + mv[i].second] != '.') {
                visited[cur.first + mv[i].first][cur.second + mv[i].second] =
                    true;
                dist[cur.first + mv[i].first][cur.second + mv[i].second] =
                    dist[cur.first][cur.second];
                if (a[cur.first][cur.second] ==
                    a[cur.first + mv[i].first][cur.second + mv[i].second]) {
                    bfs.push_front(
                        {cur.first + mv[i].first, cur.second + mv[i].second});
                } else {
                    bfs.push_back(
                        {cur.first + mv[i].first, cur.second + mv[i].second});
                    dist[cur.first + mv[i].first][cur.second + mv[i].second]++;
                }
            }
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) ans = max(dist[i][j], ans);
    cout << ans << '\n';
    return 0;
}

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