#include #include #include "queue" #include struct Hamster { int rows; int cols; std::map, int> map; Hamster(int rows, int cols, const std::map, int>& map) { this->map = map; this->rows = rows; this-> cols = cols; } int bfs() { int res = 0; std::queue>> queue; std::set> visited; std::vector> pos = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; queue.push({map[{0, 0}], {0,0}}); visited.insert({0,0}); while (!queue.empty()) { auto el = queue.front(); int posX = el.second.first; int posY = el.second.second; queue.pop(); if (posX == rows-1 && posY == cols-1) { if (el.first > res) { res = el.first; } } else { for (int x = 0 ; x < 4; x++) { if (posX + pos[x].first >= 0 && posX + pos[x].first < rows && posY + pos[x].second >= 0 && posY + pos[x].second < cols) { if (!visited.contains({posX + pos[x].first, posY + pos[x].second})) { queue.push({el.first + map[{posX + pos[x].first, posY + pos[x].second}], {posX + pos[x].first, posY + pos[x].second}}); } } } visited.insert({posX, posY}); } } return res; } }; int main() { int rows = 0; int cols = 0; std::cin >> rows; std::cin >> cols; //std::cout << rows << " " << cols << std::endl; std::map, int> map1; int tmp; int sum = 0; for (int x = 0; x> tmp; sum += tmp; map1.insert({{x, y}, tmp}); } } if (rows%2 == 1 || cols%2==1) { std::cout << sum << std::endl; } else { Hamster hamster(rows, cols, map1); std::cout << hamster.bfs() << std::endl; } return 0; }