mirror of
https://gitlab.com/mfocko/Codeforces.git
synced 2024-11-06 04:19:07 +01:00
198 lines
3.6 KiB
C++
198 lines
3.6 KiB
C++
|
#include <algorithm>
|
|||
|
#include <cassert>
|
|||
|
#include <cctype>
|
|||
|
#include <cstdint>
|
|||
|
#include <functional>
|
|||
|
#include <iostream>
|
|||
|
#include <optional>
|
|||
|
#include <queue>
|
|||
|
#include <sstream>
|
|||
|
#include <string>
|
|||
|
#include <vector>
|
|||
|
|
|||
|
namespace helpers {
|
|||
|
|
|||
|
using namespace std;
|
|||
|
|
|||
|
namespace math {
|
|||
|
long pow(long base, long exp) {
|
|||
|
if (exp == 0) return 1;
|
|||
|
long half = pow(base, exp / 2);
|
|||
|
if (exp % 2 == 0) return half * half;
|
|||
|
return half * half * base;
|
|||
|
}
|
|||
|
} // namespace math
|
|||
|
|
|||
|
namespace input {
|
|||
|
|
|||
|
template <typename T>
|
|||
|
std::vector<T> load_vector(std::size_t size) {
|
|||
|
std::vector<T> result{};
|
|||
|
|
|||
|
for (auto i = 0u; i < size; ++i) {
|
|||
|
T x;
|
|||
|
std::cin >> x;
|
|||
|
result.push_back(std::move(x));
|
|||
|
}
|
|||
|
|
|||
|
return result;
|
|||
|
}
|
|||
|
|
|||
|
} // namespace input
|
|||
|
|
|||
|
namespace output {
|
|||
|
|
|||
|
template <typename T>
|
|||
|
inline void answer(const T& ans) {
|
|||
|
cout << ans << "\n";
|
|||
|
}
|
|||
|
|
|||
|
inline void yes() { cout << "YES\n"; }
|
|||
|
inline void no() { cout << "NO\n"; }
|
|||
|
|
|||
|
inline void yesno(bool ans) {
|
|||
|
if (ans) {
|
|||
|
yes();
|
|||
|
} else {
|
|||
|
no();
|
|||
|
}
|
|||
|
}
|
|||
|
|
|||
|
} // namespace output
|
|||
|
|
|||
|
using namespace math;
|
|||
|
using namespace input;
|
|||
|
using namespace output;
|
|||
|
|
|||
|
#define LOOP(n) for (auto i = 0; i < n; ++i)
|
|||
|
|
|||
|
} // namespace helpers
|
|||
|
|
|||
|
// for ‹N› test cases, uncomment for single test case
|
|||
|
// #define SINGLE
|
|||
|
|
|||
|
namespace solution {
|
|||
|
|
|||
|
using namespace std;
|
|||
|
using namespace helpers;
|
|||
|
|
|||
|
int run_bfs(vector<vector<int>>& grid, int y0, int x0) {
|
|||
|
int volume = 0;
|
|||
|
queue<pair<int, int>> q;
|
|||
|
|
|||
|
// handle first element separately
|
|||
|
volume += grid[y0][x0];
|
|||
|
grid[y0][x0] = 0;
|
|||
|
q.push({y0, x0});
|
|||
|
|
|||
|
while (q.size()) {
|
|||
|
auto [_y, _x] = q.front();
|
|||
|
q.pop();
|
|||
|
|
|||
|
for (auto [dy, dx] :
|
|||
|
vector<pair<int, int>>{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
|
|||
|
auto y = _y + dy;
|
|||
|
auto x = _x + dx;
|
|||
|
|
|||
|
if (y < 0 || y >= static_cast<int>(grid.size()) || x < 0 ||
|
|||
|
x >= static_cast<int>(grid[y].size()) || grid[y][x] == 0) {
|
|||
|
continue;
|
|||
|
}
|
|||
|
|
|||
|
volume += grid[y][x];
|
|||
|
grid[y][x] = 0;
|
|||
|
q.push(pair{y, x});
|
|||
|
}
|
|||
|
}
|
|||
|
|
|||
|
return volume;
|
|||
|
}
|
|||
|
|
|||
|
int largest_volume(vector<vector<int>> grid) {
|
|||
|
int largest = 0;
|
|||
|
|
|||
|
for (auto y = 0; y < static_cast<int>(grid.size()); ++y) {
|
|||
|
for (auto x = 0; x < static_cast<int>(grid[y].size()); ++x) {
|
|||
|
if (grid[y][x] == 0) {
|
|||
|
// ignore zeroes
|
|||
|
continue;
|
|||
|
}
|
|||
|
|
|||
|
largest = max(largest, run_bfs(grid, y, x));
|
|||
|
}
|
|||
|
}
|
|||
|
|
|||
|
return largest;
|
|||
|
}
|
|||
|
|
|||
|
void solve() {
|
|||
|
int n, m;
|
|||
|
cin >> n >> m;
|
|||
|
|
|||
|
vector<vector<int>> grid;
|
|||
|
LOOP(n) {
|
|||
|
auto row = load_vector<int>(m);
|
|||
|
grid.push_back(move(row));
|
|||
|
}
|
|||
|
|
|||
|
answer(largest_volume(grid));
|
|||
|
}
|
|||
|
|
|||
|
} // namespace solution
|
|||
|
|
|||
|
using namespace solution;
|
|||
|
|
|||
|
#ifdef TEST
|
|||
|
|
|||
|
#include "../.common/cpp/catch_amalgamated.hpp"
|
|||
|
|
|||
|
TEST_CASE("examples") {
|
|||
|
CHECK(largest_volume(
|
|||
|
vector{vector{1, 2, 0}, vector{3, 4, 0}, vector{0, 0, 5}}) == 10);
|
|||
|
CHECK(largest_volume(vector<vector<int>>{vector{0}}) == 0);
|
|||
|
CHECK(largest_volume(vector{
|
|||
|
vector{0, 1, 1},
|
|||
|
vector{1, 0, 1},
|
|||
|
vector{1, 1, 1},
|
|||
|
}) == 7);
|
|||
|
CHECK(largest_volume(vector{
|
|||
|
vector{1, 1, 1, 1, 1},
|
|||
|
vector{1, 0, 0, 0, 1},
|
|||
|
vector{1, 0, 5, 0, 1},
|
|||
|
vector{1, 0, 0, 0, 1},
|
|||
|
vector{1, 1, 1, 1, 1},
|
|||
|
}) == 16);
|
|||
|
CHECK(largest_volume(vector{
|
|||
|
vector{1, 1, 1, 1, 1},
|
|||
|
vector{1, 0, 0, 0, 1},
|
|||
|
vector{1, 1, 4, 0, 1},
|
|||
|
vector{1, 0, 0, 0, 1},
|
|||
|
vector{1, 1, 1, 1, 1},
|
|||
|
}) == 21);
|
|||
|
}
|
|||
|
|
|||
|
#else
|
|||
|
|
|||
|
int main(void) {
|
|||
|
|
|||
|
#ifdef SINGLE
|
|||
|
|
|||
|
solution::solve();
|
|||
|
|
|||
|
#else
|
|||
|
|
|||
|
// for multiple test cases
|
|||
|
int N;
|
|||
|
std::cin >> N >> std::ws;
|
|||
|
|
|||
|
for (auto i = 0; i < N; ++i) {
|
|||
|
solution::solve();
|
|||
|
}
|
|||
|
|
|||
|
#endif
|
|||
|
|
|||
|
return 0;
|
|||
|
}
|
|||
|
|
|||
|
#endif
|