Submission #1082694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082694		Grothendieck_505	Tracks in the Snow (BOI13_tracks)	C++14	19.79 / 100	1396 ms	314068 KiB

tracks

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int h, w;
vector<vector<char>> grid;
vector<vector<int>> component;
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

// Function to perform BFS to mark all cells in the same component
void bfs(int x, int y, int comp_id) {
    queue<pair<int, int>> q;
    q.push({x, y});
    component[x][y] = comp_id;
    
    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();
        
        for (auto [dx, dy] : directions) {
            int nx = cx + dx;
            int ny = cy + dy;
            
            if (nx >= 0 && nx < h && ny >= 0 && ny < w &&
                component[nx][ny] == -1 && grid[nx][ny] == grid[cx][cy]) {
                component[nx][ny] = comp_id;
                q.push({nx, ny});
            }
        }
    }
}

int solve() {
    component.assign(h, vector<int>(w, -1));
    int comp_id = 0;

    // Step 1: Identify all connected components of 'R' and 'F'
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (grid[i][j] != '.' && component[i][j] == -1) {
                bfs(i, j, comp_id++);
            }
        }
    }

    // Step 2: Build a graph between components (where edges exist between different track types)
    vector<vector<int>> adj(comp_id);
    vector<bool> visited(comp_id, false);

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            for (auto [dx, dy] : directions) {
                int nx = i + dx;
                int ny = j + dy;

                if (nx >= 0 && nx < h && ny >= 0 && ny < w &&
                    component[i][j] != component[nx][ny] &&
                    grid[i][j] != grid[nx][ny]) {
                    adj[component[i][j]].push_back(component[nx][ny]);
                }
            }
        }
    }

    // Step 3: Perform BFS on the component graph to find the depth of the BFS tree
    queue<int> q;
    q.push(component[0][0]);
    visited[component[0][0]] = true;
    int depth = 0;

    while (!q.empty()) {
        int level_size = q.size();
        while (level_size--) {
            int curr = q.front();
            q.pop();

            for (int neighbor : adj[curr]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        depth++;
    }

    return depth;
}

int main() {
    // Input reading
    cin >> h >> w;
    grid.resize(h, vector<char>(w));

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> grid[i][j];
        }
    }

    // Solving the problem using the above approach
    int result = solve();

    // Output the result
    cout << result << endl;

    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void bfs(int, int, int)':
tracks.cpp:20:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |         auto [cx, cy] = q.front();
      |              ^
tracks.cpp:23:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |         for (auto [dx, dy] : directions) {
      |                   ^
tracks.cpp: In function 'int solve()':
tracks.cpp:55:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |             for (auto [dx, dy] : directions) {
      |                       ^

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