第4题
在一个 n×n 的小镇中,房屋编号为 (i,j),左上角为 (1,1)。时刻 0 房屋 (1,c) 起火,其中 c≤n/2。每个单位时间内,消防员保护一座尚未着火的房屋,随后火焰从时间段开始时着火的每座房屋蔓延到所有未保护的相邻房屋;已保护房屋始终受保护。最多能救下多少座房屋? 相邻指恰有一个坐标相差 1。
详细分析依次对 i=2 到 c+1 保护两座房屋 (i,c+2-i) 与 (i,c+i-1),随后保护 j=2c+1 到 n 的 (c+1,j)。列出的房屋在保护时均尚未着火;这就是官方解答的对角线策略。