KnightCircuit2

作者：王聿中

关键词：分类讨论

题目简述

给定一个$w\times h$的网格棋盘，你可以在棋盘上任意一个位置放一个“骑士”（移动规则与国际象棋中的骑士一致），可以经过重复的点，不可以经过棋盘外的点，求最多有多少个点被访问。

$1\leq w,h\leq 45000$

分析

直觉告诉我们，当棋盘足够大的时候，棋盘上的所有点都能被访问。那么我们尝试考虑，这样的棋盘最“小”有多“大”。

我们发现，当棋盘大小为$3\times 3$时，除了中间的格点之外，所有点之间都能互达。而当棋盘大小为$3\times 4$时，我们发现，棋盘上所有的点都是联通的。

那么我们猜测，当棋盘更大时，即当$min\left( w,h\right)\geq 3$且$max\left( w,h\right)\geq 4$时，棋盘上所有的点仍然是联通的。

事实上，这显然是正确的，因为棋盘上每个$3\times 4$的子矩阵中的所有点都是联通的，而点之间的联通具有传递性。

算法一

根据分析，我们很容易得出算法一。

当$min\left( w,h\right) =1$时，“骑士”无论摆放在哪里都不能移动，因此答案为$1$。

当$min\left( w,h\right) =2$时，“骑士”摆放在左上角可取得最大答案$\lfloor \frac{max\left( w,h\right) +1}{2}\rfloor$。

当$w=h=3$时，根据分析，答案为$8$。

当以上情况均不满足时，答案为$w\ast h$。