Submission #1362327

#TimeUsernameProblemLanguageResultExecution timeMemory
1362327theoneandonlytronTracks in the Snow (BOI13_tracks)C++20
100 / 100
587 ms39336 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
vector<ll> xcord = {0,0,1,-1};
vector <ll> ycord = {1, -1, 0, 0};
struct cord{
    ll x,y;
};
void solve() {
    ll n,m;
    cin >> n >> m;
    vector <vector <char>> l1(n);
    vector <vector <bool>> visited(n+1, vector<bool>(m, false));
    for (int i = 0; i < n; i++){
        string s;
        cin >> s;
        for (auto &p : s){
            l1[i].push_back(p);
        }
    }
    queue <cord> rabbits;
    queue <cord> foxes;
    auto selection = [&](ll x, ll y){
        if (visited[x][y]){
            return;
        }
        visited[x][y] = true;
        if (l1[x][y] == 'F'){
            foxes.push({x,y});
        }
        else if (l1[x][y] == 'R'){
            rabbits.push({x,y});
        }
    };
    auto flag = [&](ll x, ll y){
        if (x >= 0 && x < n && y >= 0 && y < m && (l1[x][y] == 'R' || l1[x][y] == 'F')){
            return true;
        }
        return false;
    };
    selection(0LL,0LL);
    ll answ = 0;
    while (rabbits.size() >= 1 || foxes.size() >= 1){
        if(rabbits.size() >= 1){
            answ += 1;
        }
        while (rabbits.size() >= 1){
            auto cur = rabbits.front();
            rabbits.pop();
            visited[cur.x][cur.y] = true;
            for (int i = 0; i < 4; i++){
                if (flag(cur.x + xcord[i], cur.y + ycord[i])){
                    selection(cur.x + xcord[i], cur.y + ycord[i]);
                }
            }
        }
        if(foxes.size() >= 1){
            answ += 1;
        }
        while (foxes.size() >= 1){
            auto cur = foxes.front();
            foxes.pop();
            visited[cur.x][cur.y] = true;
            for (int i = 0; i < 4; i++){
                if (flag(cur.x + xcord[i], cur.y + ycord[i])){
                    selection(cur.x + xcord[i], cur.y + ycord[i]);
                }
            }
        }
    }
    cout << answ << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...