Submission #1133858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133858		sidripper	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	811 ms	83908 KiB

tracks

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

void dfs(int start_row, int start_col, int H, int W, vector<vector<char>>& grid, vector<vector<bool>>& visited, int& rabbit, int& fox) {
    // Directions for moving up, down, left, and right
    vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    stack<pair<int, int>> stk;
    stk.push({start_row, start_col});

    while (!stk.empty()) {
        auto [row, col] = stk.top();
        stk.pop();

        // Mark as visited
        visited[row][col] = true;

        // Update animal flags
        if (grid[row][col] == 'R') rabbit = 1;
        if (grid[row][col] == 'F') fox = 1;

        // Explore neighbors
        for (auto [dr, dc] : directions) {
            int new_row = row + dr, new_col = col + dc;

            // Check bounds and if already visited
            if (new_row >= 0 && new_row < H && new_col >= 0 && new_col < W &&
                !visited[new_row][new_col] && grid[new_row][new_col] != '.') {
                stk.push({new_row, new_col});
                visited[new_row][new_col] = true; // Mark visited to avoid multiple pushes
            }
        }
    }
}

int main() {
    int H, W;
    cin >> H >> W;

    vector<vector<char>> grid(H, vector<char>(W));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> visited(H, vector<bool>(W, false));
    int ans = 0;

    for (int row = 0; row < H; row++) {
        for (int col = 0; col < W; col++) {
            // Skip visited cells or untouched snow
            if (grid[row][col] == '.' || visited[row][col]) continue;

            // Initialize animal trackers
            int rabbit = 0, fox = 0;

            // Explore connected component
            dfs(row, col, H, W, grid, visited, rabbit, fox);

            // Add contributions to the answer
            ans += rabbit;
            ans += fox;
        }
    }

    cout << ans << endl;
    return 0;
}

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