Submission #1186763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186763		pxsit	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	200 ms	20412 KiB

tracks

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <vector> // Ensure vector is included

using namespace std;

int H, W; // Height and Width of the meadow grid
vector<string> meadow; // Stores the map of the meadow
// Use vector<vector<bool>> for visited array to handle large dimensions dynamically
// Declared globally to avoid passing large structures repeatedly or stack overflow issues with large grids
vector<vector<bool>> visited; 

// Function to check if coordinates (r, c) are within the grid bounds
bool is_valid(int r, int c) {
    return r >= 0 && r < H && c >= 0 && c < W;
}

// Function to check if a path exists from the top-left cell (0,0) 
// to the bottom-right cell (H-1, W-1) using only cells of the specified 'type' ('R' or 'F').
// Uses Breadth-First Search (BFS).
bool check_path(char type) {
    // The path must start at cell (0,0). 
    // Check if the starting cell (0,0) has the required track type.
    if (meadow[0][0] != type) {
        // If the starting cell isn't the required type, no path consisting solely of this type can start from (0,0).
        return false; 
    }

    // Initialize BFS queue. Stores pairs of {row, column}.
    queue<pair<int, int>> q;
    
    // Reset visited array for this specific path check.
    // `assign` resizes the outer vector to H elements, each being a vector<bool> of size W initialized to false.
    // This is efficient and ensures clean state for each BFS run.
    visited.assign(H, vector<bool>(W, false)); 

    // Start BFS from the top-left cell (0,0)
    q.push({0, 0});
    visited[0][0] = true; // Mark the starting cell as visited

    // Define movement directions: Up, Down, Left, Right
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    // Continue BFS as long as there are cells in the queue to explore
    while (!q.empty()) {
        // Get the current cell from the front of the queue
        pair<int, int> curr = q.front();
        q.pop(); // Remove the current cell from the queue

        int r = curr.first; // Current row
        int c = curr.second; // Current column

        // Check if we reached the destination cell (H-1, W-1)
        if (r == H - 1 && c == W - 1) {
            return true; // Path found
        }

        // Explore adjacent cells (neighbors)
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i]; // Neighbor row
            int nc = c + dc[i]; // Neighbor column

            // Check if the neighbor cell is valid:
            // 1. Within grid bounds (is_valid)
            // 2. Contains the required track type (meadow[nr][nc] == type)
            // 3. Has not been visited yet in this BFS run (!visited[nr][nc])
            if (is_valid(nr, nc) && meadow[nr][nc] == type && !visited[nr][nc]) {
                visited[nr][nc] = true; // Mark the neighbor as visited
                q.push({nr, nc}); // Add the neighbor to the queue for further exploration
            }
        }
    }

    // If the queue becomes empty and the destination was not reached, then no path exists.
    return false;
}


int main() {
    // Use faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read grid dimensions H (height) and W (width)
    cin >> H >> W;
    
    // Read the meadow map into the vector of strings
    meadow.resize(H);
    bool has_R = false; // Flag to track if any 'R' tracks exist
    bool has_F = false; // Flag to track if any 'F' tracks exist
    for (int i = 0; i < H; ++i) {
        cin >> meadow[i];
        // Check for the presence of 'R' and 'F' tracks while reading
        // Optimization: stop checking row characters once both types are found
        if (!has_R || !has_F) {
           for (char c : meadow[i]) {
                if (c == 'R') has_R = true;
                if (c == 'F') has_F = true;
                // If both types found, no need to check further in this row or subsequent rows
                if (has_R && has_F) break; 
            }
        }
    }

    // The problem guarantees at least one track exists on the meadow.

    // Case 1: Only Rabbit ('R') tracks exist
    if (has_R && !has_F) {
        // The problem implies a solution always exists. If only R tracks are present,
        // it must be possible to explain the tracks with N=1 animal (a rabbit).
        // We technically don't need to call check_path('R') because existence is guaranteed by the problem statement.
        cout << 1 << endl;
    } 
    // Case 2: Only Fox ('F') tracks exist
    else if (!has_R && has_F) {
        // Similarly, if only F tracks exist, N=1 must be possible (a fox).
        cout << 1 << endl;
    } 
    // Case 3: Both Rabbit ('R') and Fox ('F') tracks exist
    else {
        // Check if a path exists from (0,0) to (H-1, W-1) using only 'R' cells.
        bool path_R_exists = check_path('R');
        // Check if a path exists from (0,0) to (H-1, W-1) using only 'F' cells.
        bool path_F_exists = check_path('F');

        // If a path exists using only 'R' cells OR using only 'F' cells,
        // then the minimum number of animals required is N=2.
        // If path_R exists, sequence (F, R) could work.
        // If path_F exists, sequence (R, F) could work.
        // Based on simplified logic derived from analyzing the problem constraints and state updates.
        if (path_R_exists || path_F_exists) {
            cout << 2 << endl;
        } else {
            // If neither a pure 'R' path nor a pure 'F' path exists from start to end,
            // then N=2 is not possible according to the logic.
            // The minimal possible number N must be at least 3.
            // Since the problem guarantees a solution exists, N=3 must be the minimum possible value.
            cout << 3 << endl;
        }
    }

    return 0;
}

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