Submission #134094

#	Time	Username	Problem	Language	Result	Execution time	Memory
134094		fredbr	Tracks in the Snow (BOI13_tracks)	C++17	34.17 / 100	1098 ms	621560 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

int const maxn = 4010;

short cnt = 0;
short n, m;
char vis[maxn][maxn];
char v[maxn][maxn];

using ii = pair<short, short>;

vector<ii> nxt, nxt2;

static int const dx[] = {0, 1, 0, -1};
static int const dy[] = {1, 0, -1, 0};

void dfs(short x, short y) {

    if (vis[x][y] == 2) return;
    if (v[x][y] == '.') return;

    vis[x][y] = 2;
    cnt--;

    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];

        if (xx >= 0 and xx < n and yy >= 0 and yy < m) {
            if (vis[xx][yy] != 0) continue;

            if (v[xx][yy] == v[x][y]) dfs(xx, yy);
            else if (v[xx][yy] != '.' and vis[xx][yy] == 0) {
                vis[xx][yy] = 1;
                nxt.emplace_back(xx, yy);
            }
        }
    }
    v[x][y] = '.';
}

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

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> v[i][j];
            if (v[i][j] != '.') cnt++;
        }
    }

    int ans = 0;
    nxt.emplace_back(0, 0);
    nxt.emplace_back(n-1, m-1);

    nxt.reserve(n*m);
    nxt2.reserve(n*m);
    
    while (cnt > 0) {
        swap(nxt, nxt2);

        for (auto i : nxt2) {
            dfs(i.first, i.second);
        }

        nxt2.clear();
        ans++;
    }

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

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