Submission #535239

#	Time	Username	Problem	Language	Result	Execution time	Memory
535239		Baray	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1054 ms	834248 KiB

tracks

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

#define gecmio_ulan cin.tie(0);ios_base::sync_with_stdio(false);

int n, m;
int explored = 0;
int mat[4005][4005];
queue<pair<int, int> > a;

void dfs(int y, int x, int type) {
    if (x >= m || y >= n || x < 0 || y < 0) return;
    if (mat[y][x] == 2) return;
    if (mat[y][x] != type) {
        a.push({y, x});
        return;
    }

    explored++;
    mat[y][x] = 2;

    dfs(y + 1, x, type);
    dfs(y - 1, x, type);
    dfs(y, x + 1, type);
    dfs(y, x - 1, type);
}

int main() {
    gecmio_ulan
    cin >> n >> m;

    char c;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c;
            if (c == 'R') {
                mat[i][j] = 0;
            }
            else if (c == 'F') {
                mat[i][j] = 1;
            }
            else {
                mat[i][j] = 2;
                explored++;
            }
        }
    }

    int ans = 0;
    bool cur;

    if (mat[0][0] == 0)cur = 0;
    else cur = 1;

    a.push({0, 0});

    while (explored != m * n) {
        while (a.size()) {
            pair<int, int> tmp = a.front();
            a.pop();

            if (mat[tmp.first][tmp.second] == 2) continue;
            else if (mat[tmp.first][tmp.second] != cur) {
                a.push({tmp.first, tmp.second});
                break;
            }

            dfs(tmp.first, tmp.second, cur);
        }
        
        ans++;
        cur = !cur;
    }

    cout << ans << "\n";
}

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