#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, std::pair>> queue; //std::set>> visited; std::vector> pos = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; std::map, std::pair>, std::pair, std::pair>> pred; queue.push({{map[{0, 0}],0}, {0,0}}); //visited.insert({map[{0, 0}], {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.first > res) { res = el.first.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) { std::pair, std::pair> p = {{el.first.first, el.first.second}, {posX, posY}}; bool f = false; int pred_c = 1; if ((posX + pos[x].first) == 0 && (posY + pos[x].second)==0) { continue; } while (p.second.first != 0 || p.second.second != 0) { if (p.second.first == (posX + pos[x].first) && p.second.second == (posY + pos[x].second)) { f = true; break; } pred_c++; p = pred[p]; } if (!f) { queue.push({{el.first.first + map[{posX + pos[x].first, posY + pos[x].second}], el.first.second+1}, {posX + pos[x].first, posY + pos[x].second}}); //visited.insert({el.first + map[{posX + pos[x].first, posY + pos[x].second}], {posX + pos[x].first, posY + pos[x].second}}); pred.insert({{{el.first.first + map[{posX + pos[x].first, posY + pos[x].second}], pred_c}, {posX + pos[x].first, posY + pos[x].second}}, {{el.first.first, el.first.second}, {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; }