Submission #1235545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235545		jiayiiyaij	Tracks in the Snow (BOI13_tracks)	C++17	58.44 / 100	2098 ms	79096 KiB

tracks

#include <iostream>
#include <vector>
#include<queue>
#include <algorithm>
using namespace std;

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int H, W;
    cin >> H >> W;
    cin.ignore();

    vector<vector<char>> mapp(H, vector<char>(W));
    for (int i=0; i<H; i++) {
        string line;
        cin >> line;
        for (int j=0; j<W; j++) {
            mapp[i][j] = line[j];
        }
    }
    
    vector<char> ani(2, '.');
    if (mapp[0][0] == 'R') ani = {'R', 'F'};
    else ani = {'F', 'R'};

    int dirs[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
    int count = 0;
    bool flag0 = false, flag1 = false;
    
    vector<vector<int>> vis(H, vector<int>(W, 0));
    int vid = 1;  // visit ID trick
    
    while(true) {
        flag0 = false;
        flag1 = false;
        deque<pair<int, int>> q;
        q.push_back({0,0});
        vis[0][0] = vid;
        
        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop_front();

            for (int i = 0; i < 4; i++) {
                int rr = r + dirs[i][0];
                int cc = c + dirs[i][1];
                if (rr < 0 || rr >= H || cc < 0 || cc >= W) continue;
                if (vis[rr][cc] == vid) continue;
                if (mapp[rr][cc] == '.') continue;

                if (mapp[r][c] == ani[0] || mapp[r][c] == '#') {
                    if (mapp[rr][cc] == ani[0] || mapp[r][c] == ani[0]) flag0 = true;
                    if (mapp[rr][cc] == ani[1]) flag1 = true;
                    q.push_back({rr, cc});
                    vis[rr][cc] = vid;
                }

                if (mapp[r][c] == ani[1]) {
                    if (mapp[rr][cc] == ani[1] || mapp[rr][cc] == '#') {
                        q.push_back({rr, cc});
                        vis[rr][cc] = vid;
                    }
                }
            }

            mapp[r][c] = '#';
        }
        
        if (not flag0) break;
        count += 1;
        if (not flag1) break;
        count += 1;

        vid++;
    }

    cout << count << '\n';
}

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