제출 #1209625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209625		maihoondawn	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	875 ms	250804 KiB

tracks

#include <bits/stdc++.h>

using namespace std;
#define int long long

vector<pair<int, int>> dir;

void solve(){
    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];
        }
    }

    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) 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;
    while (!q.empty()){
        pair<int, int> oh = q.front();
        real.push(oh);
        q.pop();
        for (auto w : dir){
            if (!check(w.first + oh.first, w.second + oh.second)) continue;
            else if (visited[w.first + oh.first][w.second + oh.second]) continue;
            else if (fox && v[w.first + oh.first][w.second + oh.second] == 'R') continue;
            else if (!fox && v[w.first + oh.first][w.second + oh.second] == 'F') continue;
            visited[w.first + oh.first][w.second + oh.second] = true;
            q.push({w.first + oh.first, w.second + oh.second});
        }
    }

    // at this point fox only tells me the state of shit in the queue

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

    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: 0 / 30
• Subtask 2: 2.1875 / 70