Submission #1202328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202328		zarcx	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	745 ms	93480 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>> visited(h, vector<int>(w, 0));
    vector<pair<int, int>> dir = {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };
    
    // int ans = 0;
    set<int> count;
    for(int i = 0; i < h; i++)
    {
        for(int j = 0; j < w; j++)
        {
            if(visited[i][j] || grid[i][j] == '.')
                continue;

            visited[i][j] = 1;

            queue<pair<int, int>> q;
            count.insert(grid[i][j]);
            q.push({i, j});
            
            while(!q.empty())
            {
                auto [y, x] = q.front();
                q.pop();

                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(visited[nY][nX] || grid[nY][nX] == '.')
                        continue;

                    visited[nY][nX] = 1;
                    count.insert(grid[nY][nX]);
                    q.push({nY, nX});
                }
            }

            // ans += count.size();
        }
    }

    cout << count.size() << endl;

    return 0;
}

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