#include #include #include #include struct Field { int width, height; std::pair end; std::vector> field; Field(int width, int height) { field.reserve(height); this->width = width; this->height = height; end = {width - 1, height -1}; } bool isValidPos(std::pair pos) { return !(pos.first < 0 || pos.second < 0 || pos.first >= width || pos.second >= height); } int operator[](const std::pair &pos) { return field[pos.second][pos.first]; } }; int dfs(Field &field, std::set> &seen, std::pair pos, int sum) { int value = field[pos]; if (pos == field.end) return sum + value; seen.insert(pos); int max = 0; for (int i = 0; i < 4; i++) { auto new_pos = pos; switch (i) { // UP case 0: new_pos.second -= 1; break; // DOWN case 1: new_pos.second += 1; break; // LEFT case 2: new_pos.first -= 1; break; // RIGHT case 3: new_pos.first += 1; break; } if (!field.isValidPos(new_pos) || seen.contains(new_pos)) continue; int res = dfs(field, seen, new_pos, sum + value); max = std::max(res, max); } seen.erase(pos); return max; } int main() { int height, width; std::cin >> height >> width; Field field = Field(width, height); int full_sum = 0; std::vector sums; sums.reserve(height); for (int h = 0; h < height; h++) { std::vector row; row.reserve(width); int sum = 0; int num; for (int w = 0; w < width; w++) { std::cin >> num; sum += num; row.push_back(num); } full_sum += sum; sums.push_back(sum); field.field.emplace_back(row); } int res = full_sum; if (height % 2 == 0 && width % 2 == 0) { std::set> seen; res = dfs(field, seen, {0,0}, 0); } std::cout << res << std::endl; return 0; }