Submission #1310227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310227		s101g	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	900 ms	110816 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> dr{-1, 1, 0, 0}, dc{0, 0, 1, -1};
const int inf = 1e9;
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    }
    deque<pair<int, int>> q;
    q.push_back({0, 0});
    vector<vector<int>> d(n, vector<int>(m, inf));
    d[0][0] = 1;
    int ans = 1;
    while (!q.empty())
    {
        auto cur = q.front();
        q.pop_front();
        int r = cur.first, c = cur.second;
        ans = max(ans, d[r][c]);
        for (int i = 0; i < 4; i++)
        {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr < 0 || nc < 0 || nr >= n || nc >= m || a[nr][nc] == '.')
                continue;
            if (d[nr][nc] == inf)
            {
                if (a[nr][nc] == a[r][c])
                {
                    d[nr][nc] = d[r][c];
                    q.push_front({nr, nc});
                }
                else
                {
                    q.push_back({nr, nc});
                    d[nr][nc] = d[r][c] + 1;
                }
            }
        }
    }
    cout << ans;
    return 0;
}

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