Câu hỏi 4
Một thị trấn nhỏ có $n \times n$ ngôi nhà, được đánh chỉ số $(i, j)$ với $1 \leq i, j \leq n$; nhà $(1,1)$ ở góc trên bên trái, trong đó $i$ và $j$ lần lượt là chỉ số hàng và cột. Tại thời điểm $0$, đám cháy bắt đầu ở nhà $(1, c)$, với $c \leq \frac{n}{2}$. Trong mỗi khoảng thời gian tiếp theo $[t, t+1]$, lính cứu hỏa bảo vệ một ngôi nhà chưa cháy, đồng thời lửa lan đến mọi nhà lân cận chưa được bảo vệ của các nhà đang cháy ở thời điểm $t$. Một nhà đã được bảo vệ sẽ luôn được bảo vệ. Quá trình kết thúc khi lửa không thể lan thêm. Lính cứu hỏa có thể cứu được nhiều nhất bao nhiêu ngôi nhà? Nhà $(i, j)$ là nhà lân cận của nhà $(k, \ell)$ nếu $|i-k|+|j-\ell|=1$.