Submission #917149

#	Time	Username	Problem	Language	Result	Execution time	Memory
917149		0x34c	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	891 ms	781460 KiB

tracks

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'

using namespace std;

int N, M;
vector<vector<bool>> vis;
vector<vector<char>> grid;
queue<pii> q;
int mvt[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void dfs(int r, int c, char let)
{
    if (r < 0 || c < 0 || r >= N || c >= M || grid[r][c] == '.' || vis[r][c])
        return;

    if (grid[r][c] != let)
    {
        q.push({r, c});
        return;
    }

    vis[r][c] = true;
    for (int i = 0; i < 4; i++)
    {
        int rx = r + mvt[i][0], cx = c + mvt[i][1];
        dfs(rx, cx, let);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    grid.resize(N, vector<char>(M));
    vis.resize(N, vector<bool>(M, false));

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> grid[i][j];

    q.push({0, 0});
    int res = 0;
    while (!q.empty())
    {
        int sz = q.size();
        for (int _ = 0; _ < sz; _++)
        {
            int r, c;
            tie(r, c) = q.front();
            q.pop();

            dfs(r, c, grid[r][c]);
        }
        ++res;
    }

    cout << res << endl;
}

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