Submission #1255337

#TimeUsernameProblemLanguageResultExecution timeMemory
1255337MisterReaperTracks in the Snow (BOI13_tracks)C++20
0 / 100
1276 ms1114112 KiB
// File U.cpp created on 09.08.2025 at 00:46:23 #include <bits/stdc++.h> using i64 = long long; #ifdef DEBUG #include "/home/ahmetalp/Desktop/Workplace/debug.h" #else #define debug(...) void(23) #endif constexpr int max_N = int(4000) + 5; int N, M; char A[max_N][max_N]; bool vis1[max_N][max_N]; bool vis2[max_N][max_N]; constexpr int dx[] = {0, +1, 0, -1}; constexpr int dy[] = {+1, 0, -1, 0}; std::vector<std::pair<int, int>> pnts; void dfs1(int x, int y) { vis1[x][y] = true; pnts.emplace_back(x, y); for (int d = 0; d < 4; ++d) { int nx = x + dx[d], ny = y + dy[d]; if (0 <= nx && nx < N && 0 <= ny && ny < M && A[nx][ny] != '.' && vis1[nx][ny] == false) { dfs1(nx, ny); } } } void dfs2(int x, int y) { vis2[x][y] = true; for (int d = 0; d < 4; ++d) { int nx = x + dx[d], ny = y + dy[d]; if (0 <= nx && nx < N && 0 <= ny && ny < M && A[nx][ny] == A[x][y] && vis2[nx][ny] == false) { dfs2(nx, ny); } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> N >> M; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { std::cin >> A[i][j]; } } int ans = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { if (A[i][j] == '.' || vis1[i][j]) { continue; } dfs1(i, j); int cnt[2] {}; for (auto[x, y] : pnts) { if (vis2[x][y]) { continue; } dfs2(x, y); cnt[A[x][y] == 'F'] += 1; } ans += std::min(cnt[0], cnt[1]) + 1; pnts.clear(); } } std::cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...