2005 APMO 第 4 题

In a small town, there are $n \times n$ houses indexed by $(i, j)$ for $1 \leq i, j \leq n$ with $(1,1)$ being the house at the top left corner, where $i$ and $j$ are the row and column indices, respectively. At time 0 , a fire breaks out at the house indexed by $(1, c)$, where $c \leq \frac{n}{2}$. During each subsequent time interval $[t, t+1]$, the fire fighters defend a house which is not yet on fire while the fire spreads to all undefended neighbors of each house which was on fire at time $t$. Once a house is defended, it remains so all the time. The process ends when the fire can no longer spread. At most how many houses can be saved by the fire fighters? A house indexed by $(i, j)$ is a neighbor of a house indexed by $(k, \ell)$ if $|i-k|+|j-\ell|=1$.

在一个小镇上，有 $n \times n$ 个房屋，索引为 $(i, j)$，即 $1 \leq i, j \leq n$，其中 $(1,1)$ 是左上角的房屋，其中 $i$ 和 $j$ 分别是行索引和列索引。在时间 0 ，索引为 $(1, c)$ 的房屋发生火灾，其中 $c \leq \frac{n}{2}$。在随后的每个时间间隔 $[t, t+1]$ 中，消防员保卫尚未着火的房屋，同时火势蔓延到在时间 $t$ 着火的每栋房屋的所有未设防的邻居。一旦房屋受到保卫，它就会一直如此。当火不再蔓延时，该过程结束。消防员最多能拯救多少间房屋？如果 $|i-k|+|j-\ell|=1$，则由 $(i, j)$ 索引的房屋是由 $(k, \ell)$ 索引的房屋的邻居。