Submission #880003

#	Time	Username	Problem	Language	Result	Execution time	Memory
880003		SpyrosAliv	Tracks in the Snow (BOI13_tracks)	C++14	43.13 / 100	2096 ms	36440 KiB

tracks

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

vector<vector<char>> grid(4001, vector<char>(4001));
vector<vector<bool>> visited(4001, vector<bool>(4001, false));
vector<pair<int, int>> delta = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
map<char, char> hm;
int n, m, steps = 0;

bool inBounds(int i, int j) {
    if (i < 0 || i >= n || j < 0 || j >= m) return 0;
    return 1;
}

void bfs() {
    int i = n-1, j = m-1;
    queue<pair<int, int>> q;
    q.push({i, j});
    vector<vector<bool>> bfsVisited(n, vector<bool>(m, false));
    bfsVisited[i][j] = true;
    while (!q.empty()) {
        int currRow = q.front().first;
        int currCol = q.front().second;
        grid[currRow][currCol] = hm[grid[currRow][currCol]];
        if (!visited[currRow][currCol]) {
            visited[currRow][currCol] = true;
            steps--;
        }
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nextRow = currRow + delta[i].first;
            int nextCol = currCol + delta[i].second;
            if (inBounds(nextRow, nextCol) 
                && !bfsVisited[nextRow][nextCol] 
                && grid[nextRow][nextCol] != '.'
                && grid[nextRow][nextCol] != grid[currRow][currCol]) {
                q.push({nextRow, nextCol});
                bfsVisited[nextRow][nextCol] = true;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    hm['F'] = 'R';
    hm['R'] = 'F';
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == '.') visited[i][j] = true;
            else steps++;
        }
    }
    int animals = 0;
    while (steps > 0) {
        animals++;
        bfs();
    }
    cout << animals << "\n";
    return 0;
}

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