Submission #1209837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209837		maihoondawn	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1143 ms	225624 KiB

tracks

#include <bits/stdc++.h>

using namespace std;
#define int long long

vector<pair<int, int>> dir;

void solve(){
    int cnt = 0;
    int h, w; cin >> h >> w;
    vector<vector<char>> v(h, vector<char>(w, '.'));
    for (int i = 0; i < h; i ++){
        for (int j = 0; j < w; j ++){
            cin >> v[i][j];
            if (v[i][j] != '.') cnt ++;
        }
    }

    bool fox = false;
    if (v[0][0] == 'F') fox = true;
    auto check = [&](int i, int j) -> bool {
        if (i >= 0 && i < h && j >= 0 && j < w && v[i][j] != '.') return true;
        else return false;
    };
    vector<vector<bool>> visited(h, vector<bool>(w, false));
    queue<pair<int, int>> q;
    q.push({0,0}); visited[0][0] = true;
    int ans = 1;
    queue<pair<int, int>> real;
    bool creation = true;
    while (true){
        if (creation){
            while (!q.empty()){
                pair<int, int> oh = q.front();
                q.pop();
                real.push(oh);
                for (auto w : dir){
                    int x = w.first + oh.first; int y = w.second + oh.second;
                    if (check(x,y) && !visited[x][y]){
                        if ((fox && v[x][y] == 'F') || (!fox && v[x][y] == 'R')) {q.push({x,y}); visited[x][y] = true;}
                    }
                }
            }
            creation = false;
        }

        if (!creation){
            bool flag = false;
            while (!real.empty()){
                pair<int, int> oh = real.front();
                real.pop();
                for (auto w : dir){
                    int x = oh.first + w.first;
                    int y = oh.second + w.second;
                    if (!check(x,y) || visited[x][y]) continue;
                    if (fox && v[x][y] == 'R'){
                        visited[x][y] = true; q.push({x,y});
                        flag = true;
                    }
                    if (!fox && v[x][y] == 'F'){
                        visited[x][y] = true; q.push({x,y});
                        flag = true;
                    }
                }
            }
            if (flag) {ans ++; fox = !fox;}
            else break;
            creation = true;
        }
    }

    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    dir.push_back({0,1}); dir.push_back({-1,0}); dir.push_back({1,0}); dir.push_back({0,-1});
    while (t --){
        solve();
    }
    return 0;
}

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