Submission #450046

#	Time	Username	Problem	Language	Result	Execution time	Memory
450046		four_specks	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1122 ms	152436 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int h, w;
    cin >> h >> w;

    vector<vector<int>> grid(h, vector<int>(w));
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            char c;
            cin >> c;

            if (c == '.')
                grid[i][j] = 0;
            else if (c == 'R')
                grid[i][j] = 1;
            else if (c == 'F')
                grid[i][j] = 2;
        }
    }

    int n = 0;

    vector<vector<int>> d(h, vector<int>(w, 0));
    deque<pair<int, int>> dq;
    for (dq.emplace_front(0, 0), d[0][0] = 1; !dq.empty();)
    {
        auto [y, x] = dq.front();
        dq.pop_front();
        n = max(n, d[y][x]);
        for (auto [dx, dy] : {pair(0, -1), pair(0, 1), pair(-1, 0), pair(1, 0)})
        {
            if (x + dx >= 0 && x + dx < w && y + dy >= 0 && y + dy < h)
            {
                if (grid[y + dy][x + dx] && d[y + dy][x + dx] == 0)
                {
                    if (grid[y + dy][x + dx] == grid[y][x])
                    {
                        d[y + dy][x + dx] = d[y][x];
                        dq.emplace_front(y + dy, x + dx);
                    }
                    else
                    {
                        d[y + dy][x + dx] = d[y][x] + 1;
                        dq.emplace_back(y + dy, x + dx);
                    }
                }
            }
        }
    }

    cout << n << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

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