// 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |