#include #include #include #include #include #include #include #include #include #include #include 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 std::vector load_vector(std::size_t size) { std::vector 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 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>& grid, int y0, int x0) { int volume = 0; queue> 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>{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) { auto y = _y + dy; auto x = _x + dx; if (y < 0 || y >= static_cast(grid.size()) || x < 0 || x >= static_cast(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> grid) { int largest = 0; for (auto y = 0; y < static_cast(grid.size()); ++y) { for (auto x = 0; x < static_cast(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> grid; LOOP(n) { auto row = load_vector(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{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