Submission #1235550

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

tracks

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

#define AT(grid, r, c) (grid[(r) * W + (c)])

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

    int H, W;
    cin >> H >> W;

    vector<char> mapp(H * W);
    for (int i = 0; i < H; ++i) {
        string line;
        cin >> line;
        for (int j = 0; j < W; ++j) {
            AT(mapp, i, j) = line[j];
        }
    }

    char first = (AT(mapp, 0, 0) == 'R') ? 'R' : 'F';
    char second = (first == 'R') ? 'F' : 'R';
    vector<char> ani = {first, second};

    int dirs[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };

    vector<int> vis(H * W, 0);
    int vid = 1;
    int count = 0;

    while (true) {
        bool flag0 = false, flag1 = false;
        deque<pair<int, int>> q;
        q.push_back({0, 0});
        AT(vis, 0, 0) = vid;

        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop_front();

            char current = AT(mapp, r, c);

            for (int d = 0; d < 4; ++d) {
                int rr = r + dirs[d][0];
                int cc = c + dirs[d][1];
                if (rr < 0 || rr >= H || cc < 0 || cc >= W) continue;

                int idx = rr * W + cc;
                if (vis[idx] == vid) continue;
                char next = AT(mapp, rr, cc);
                if (next == '.') continue;

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

                if (current == ani[1]) {
                    if (next == ani[1] || next == '#') {
                        vis[idx] = vid;
                        q.push_back({rr, cc});
                    }
                }
            }

            AT(mapp, r, c) = '#';
        }

        if (!flag0) break;
        count += 1;
        if (!flag1) break;
        count += 1;

        vid++;
    }

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

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