Submission #892786

#	Time	Username	Problem	Language	Result	Execution time	Memory
892786		cogentcoder73	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	2062 ms	423308 KiB

tracks

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

int H, W;

vector<pair<int, int>> bfs(vector<vector<char>>& meadow, vector<vector<bool>>& visited, pair<int, int> start, char find, bool avoid) {
    vector<pair<int, int>> cc;
    queue<pair<int, int>> q; q.push(start);
    pair<int, int> cur;
    while (!q.empty()) {
        cur = q.front(); q.pop();
        if (!visited[cur.first][cur.second]) {
            visited[cur.first][cur.second] = true;
            if ((avoid && meadow[cur.first][cur.second] != find) || (!avoid && meadow[cur.first][cur.second] == find)) {
                cc.push_back(cur);
                if (cur.first > 0) q.push({cur.first - 1, cur.second});
                if (cur.first < H - 1) q.push({cur.first + 1, cur.second});
                if (cur.second > 0) q.push({cur.first, cur.second - 1});
                if (cur.second < W - 1) q.push({cur.first, cur.second + 1});
            }
        }
    }
    return cc;
}

int main() {
    cin >> H >> W;
    vector<vector<char>> meadow(H, vector<char>(W));
    for (int h = 0; h < H; h++) for (int w = 0; w < W; w++) cin >> meadow[h][w];
    vector<vector<bool>> visited(H, vector<bool>(W, false));

    vector<vector<pair<int, int>>> ccs;
    int numC = 0;
    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            if (!visited[h][w] && meadow[h][w] != '.') {
                ccs.push_back(bfs(meadow, visited, {h, w}, '.', true));
            }
        }
    }

    vector<vector<bool>> visitedR(H, vector<bool>(W, false));
    vector<vector<bool>> visitedF(H, vector<bool>(W, false));

    int curR, curF;
    int ans = 0;

    for (vector<pair<int, int>> cc : ccs) {
        curR = 0;
        curF = 0;
        for (pair<int, int> p : cc) {
            if (!visitedR[p.first][p.second] && meadow[p.first][p.second] == 'R') {
                curR++;
                bfs(meadow, visitedR, p, 'R', false);
            }
            if (!visitedF[p.first][p.second] && meadow[p.first][p.second] == 'F') {
                curF++;
                bfs(meadow, visitedF, p, 'F', false);
            }
        }
        if (curR == 0 || curF == 0)  ans++;
        else ans += 1 + min(curR, curF);
    }

    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:33:9: warning: unused variable 'numC' [-Wunused-variable]
   33 |     int numC = 0;
      |         ^~~~

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