Submission #1202357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202357		zarcx	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	616 ms	120044 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int h, w;
    cin >> h >> w;

    vector<string> grid(h);
    for(string& s : grid)
        cin >> s;

    vector<vector<int>> depth(h, vector<int>(w, 0));
    vector<pair<int, int>> dir = {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };
    
    deque<pair<int, int>> q;
    q.push_front({0, 0});
    depth[0][0] = 1;
    
    int ans = 0;
    while(!q.empty())
    {
        auto [y, x] = q.front();
        q.pop_front();

        ans = max(ans, depth[y][x]);

        for(const auto& [dY, dX] : dir)
        {
            int nY = y + dY;
            int nX = x + dX;

            if((nY >= h)|| (nX >= w) || (nY < 0) || (nX < 0))
                continue;

            if(depth[nY][nX] || grid[nY][nX] == '.')
                continue;

            depth[nY][nX] = depth[y][x];
            if(grid[y][x] == grid[nY][nX])
            {
                q.push_front({nY, nX});
            }
            else
            {
                depth[nY][nX]++;
                q.push_back({nY, nX});
            }
        }
    }

    cout << ans << endl;

    return 0;
}

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