Submission #965554

#TimeUsernameProblemLanguageResultExecution timeMemory
965554OIaspirant2307Tracks in the Snow (BOI13_tracks)C++17
2.19 / 100
1959 ms406092 KiB
#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++; } } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ vis[i][j] = false; } } for (auto p : foxes) { if (!vis[p.f][p.s]) { bfs({p.f, p.s}); ans++; } } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...