#include #include #include void dfs(std::pair pos, std::pair endPos, std::set> & visited, int & larvas, int & maxLarvas, std::vector> & map) { if (pos.first < 0 || pos.second < 0 || pos.first > endPos.first || pos.second > endPos.second || !visited.insert(pos).second) return; larvas += map[pos.first][pos.second]; if (pos == endPos) { if (larvas > maxLarvas) maxLarvas = larvas; larvas -= map[pos.first][pos.second]; visited.erase(pos); return; } dfs({pos.first , pos.second + 1}, endPos, visited, larvas, maxLarvas, map); dfs({pos.first , pos.second - 1}, endPos, visited, larvas, maxLarvas, map); dfs({pos.first + 1, pos.second }, endPos, visited, larvas, maxLarvas, map); dfs({pos.first - 1, pos.second }, endPos, visited, larvas, maxLarvas, map); larvas -= map[pos.first][pos.second]; visited.erase(pos); } int main() { int m, n; std::cin >> n >> m; std::vector> map(n); for (int i = 0; i < n; ++i) { map[i].resize(m); for (int j = 0; j < m; ++j) std::cin >> map[i][j]; } std::set> visited; int maxLarvas = 0, larvas = 0; dfs({0, 0}, {n - 1, m - 1}, visited, larvas, maxLarvas, map); std::cout << maxLarvas << std::endl; return 0; }