This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define int long long
#define pi pair<int, int>
#define f first
#define s second
const int N = 4005;
vector<vector<char>> grid(N, vector<char>(N));
vector<vector<bool>> vis(N, vector<bool>(N, 0));
vector<pi> rabbits;
vector<pi> foxes;
vector<pi> moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n, m;
bool ok(int i, int j)
{
return (i >= 0 && i < n && j >= 0 && j < m && grid[i][j] != '.' && !vis[i][j]);
}
void bfs(pi pos)
{
queue<pi> q;
q.push({pos.f, pos.s});
vis[pos.f][pos.s] = true;
while (!q.empty())
{
auto p = q.front();
q.pop();
for (auto move : moves)
{
if (ok(p.f + move.f, p.s + move.s))
{
vis[p.f + move.f][p.s + move.s] = true;
q.push({p.f + move.f, p.s + move.s});
}
}
}
}
signed main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> grid[i][j];
if (grid[i][j] == 'R')
{
rabbits.push_back({i, j});
}
else if (grid[i][j] == 'F')
{
foxes.push_back({i, j});
}
}
}
int ans = 0;
for (auto p : rabbits)
{
if (!vis[p.f][p.s])
{
bfs({p.f, p.s});
ans++;
}
}
vis.resize(n + 1, vector<bool>(m + 1, 0));
for (auto p : foxes)
{
if (!vis[p.f][p.s])
{
bfs({p.f, p.s});
ans++;
}
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |