Câu hỏi 4
Một thị trấn có $n\times n$ ngôi nhà, đánh chỉ số $(i,j)$ với $1\le i,j\le n$; nhà $(1,1)$ ở góc trên bên trái, $i,j$ lần lượt là chỉ số hàng và cột. Lúc 0, lửa bắt đầu ở nhà $(1,c)$, trong đó $c\le 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 nhà chưa cháy, đồng thời lửa lan đến tất cả các nhà kề chưa được bảo vệ của mỗi nhà đã cháy ở thời điể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. Nhiều nhất có thể cứu được bao nhiêu nhà?
Nhà $(i,j)$ kề nhà $(k,\ell)$ nếu $|i-k|+|j-\ell|=1$.
Nhà $(i,j)$ kề nhà $(k,\ell)$ nếu $|i-k|+|j-\ell|=1$.