Submission #1125723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125723		oook	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	886 ms	208932 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define s(x) sort(x.begin(), x.end())
#define sg(x) sort(x.begin(), x.end(), greater<int>())
#define vint vector<int>
#define MOD ((int)1e9 + 7)

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

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<char>> v(n, vector<char>(m));
    vector<vector<int>> dis(n, vector<int>(m, INT_MAX));

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

    auto bfs = [&](pair<int, int> s) -> void
    {
        deque<pair<int, int>> q;
        q.push_front(s);
        dis[s.first][s.second] = 1;

        while (!q.empty())
        {
            int px = q.front().first, py = q.front().second;
            q.pop_front();
            ans = max(ans, dis[px][py]);

            for (int i = 0; i < 4; i++)
            {
                int x = px + dx[i], y = py + dy[i];

                if (x < 0 or y < 0 or x >= n or y >= m)
                    continue;
                if (v[x][y] == '.')
                    continue;

                if (v[x][y] == v[px][py] and dis[x][y] > dis[px][py])
                {
                    dis[x][y] = dis[px][py];
                    q.push_front({x, y});
                }
                else if (dis[x][y] > dis[px][py] + 1)
                {
                    dis[x][y] = dis[px][py] + 1;
                    q.push_back({x, y});
                }
            }
        }
    };
    bfs({0, 0});
    cout << ans << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#endif

    int t;
    // cin >> t;
    t = 1;
    while (t--)
        solve();

    return 0;
}

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