Submission #1333440

#TimeUsernameProblemLanguageResultExecution timeMemory
1333440flyTracks in the Snow (BOI13_tracks)C++20
49.69 / 100
2098 ms81036 KiB
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h, w;
    cin >> h >> w;
    vector<string> map(h);
    int tt = 0;
    for (int i = 0; i < h; i++) {
        cin >> map[i];
        for (char x: map[i]) {
            tt += (x!='.')? 1:0;
        }
    }
    char cur = map[0][0];
    vector<vector<int>> visited(h, vector<int>(w));
    vector<int> xdirs = {-1, 0, 1, 0};
    vector<int> ydirs = {0, -1, 0, 1};
    int ans = 0;
    deque<pair<int, int>> stack;
    while (tt > 0) {
        ans++;
        stack.push_back({0, 0});
        while (!stack.empty()) {
            auto [x, y] = stack.at(0);
            stack.pop_front();
            for (int i = 0; i < 4; i++) {
                int nx = x + xdirs[i];
                int ny = y + ydirs[i];
                if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                if ((map[nx][ny] == cur || map[nx][ny] == 'c') && visited[nx][ny] != ans) {
                    if (map[nx][ny] == cur) tt--;
                    map[nx][ny] = 'c';
                    visited[nx][ny] = ans;
                    stack.push_back({nx, ny});
                }
            }
        }
        if (cur == 'F') {
            cur = 'R';
        } else {
            cur = 'F';
        }
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...