Submission #1317884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317884		mousham	Tracks in the Snow (BOI13_tracks)	C++17	15.52 / 100	2098 ms	86112 KiB

tracks

// Problem Link: https://oj.uz/problem/view/BOI13_tracks

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

#define UNTOUCHED '.'

constexpr int DIRNS(4);
constexpr pair<int, int> MOVE[DIRNS]{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

vector<vector<char>> meadow; // NOTE: Don't use variable name map as there exists std::map in C++ STL

int count(int height, int width)
{
    vector<vector<bool>> vis(height, vector<bool>(width));
    int res = 0;

    for (int i = 0; i < height; i++)
        for (int j = 0; j < width; j++)
        {
            char curr_animal = meadow[i][j];
            if (!vis[i][j] && curr_animal != UNTOUCHED)
            {
                vector<vector<bool>> curr(height, vector<bool>(width));
                res++;
                stack<pair<int, int>> st; // h, w
                st.emplace(i, j);
                vis[i][j] = true;
                curr[i][j] = true;

                while (!st.empty())
                {
                    auto [h, w] = st.top();
                    st.pop();

                    for (int d = 0; d < DIRNS; d++)
                    {
                        int new_h = h + MOVE[d].first, new_w = w + MOVE[d].second;
                        if (new_h >= 0 && new_h < height && new_w >= 0 && new_w < width && meadow[new_h][new_w] != UNTOUCHED)
                            if (!vis[new_h][new_w] && meadow[new_h][new_w] == curr_animal)
                                vis[new_h][new_w] = true, st.emplace(new_h, new_w), curr[new_h][new_w] = true;
                            else if (vis[new_h][new_w] && !curr[new_h][new_w]) // IMP: else ALWAYS MATHES NEAREST UNMATCHED if
                                st.emplace(new_h, new_w), curr[new_h][new_w] = true;
                    }
                }
            }
        }

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    cin >> H >> W;

    meadow.assign(H, vector<char>(W));
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            cin >> meadow[i][j];

    cout << count(H, W) << '\n';
    return 0;
}

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