Submission #693808

#	Time	Username	Problem	Language	Result	Execution time	Memory
693808		Elias_Obeid	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	835 ms	126448 KiB

tracks

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

using int32 = int32_t;
using int64 = int64_t;

const int32 INF = 1'000'000'000;
const vector<int32> DX = {-1, +1, 0, 0};
const vector<int32> DY = {0, 0, -1, +1};

int32 N, M;

inline bool inGrid(int32 x, int32 y)
{
    return (0 <= x && x < N && 0 <= y && y < M);
}

int32 main()
{
    cin >> N >> M;
    vector<string> grid(N);
    for (auto &row : grid)
    {
        cin >> row;
    }

    deque<pair<int32, int32>> cells;
    vector<vector<int32>> depth(N, vector<int32>(M, INF));
    depth[0][0] = 1;
    cells.emplace_back(0, 0);

    int32 result = 0;
    while (!cells.empty())
    {
        auto [x, y] = cells.front();
        cells.pop_front();

        result = max(result, depth[x][y]);
        for (int32 d = 0; d < 4; ++d)
        {
            int32 nx = x + DX[d];
            int32 ny = y + DY[d];
            if (inGrid(nx, ny) && grid[nx][ny] != '.' && depth[nx][ny] == INF)
            {
                if (grid[nx][ny] == grid[x][y])
                {
                    depth[nx][ny] = depth[x][y];
                    cells.emplace_front(nx, ny);
                }
                else
                {
                    depth[nx][ny] = depth[x][y] + 1;
                    cells.emplace_back(nx, ny);
                }
            }
        }
    }
    cout << result << "\n";
    return 0;
}

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