Consider a 2025 × 2025 grid of unit squares. Matilda wishes to place on the grid
some rectangular tiles, possibly of different sizes, such that each side of every tile
lies on a grid line and every unit square is covered by at most one tile.
Determine the minimum number of tiles Matilda needs to place so that each row
and each column of the grid has exactly one unit square that is not covered by any
tile.
(最佳解應是2,112，該篇僅以筆記看待)
---
Answer：4047
由於每行每列都要留一格空白，這些「未覆蓋」的格子會剛好形成一個排列圖形，
也就是說，可以用一個排列 π 來表示所有空格的位置：
E = {(i, π(i)) | i = 1, 2, …, n}。
我們可以重新標號，讓排列變成 π(i) = i，
這樣未覆蓋的格子就都在主對角線上。
換句話說，所有對角線以外的格子都要被磁磚覆蓋。
---
把整個方格分成三個部分：
- 上半部：U = {(r, c) | r < c}
- 下半部：L = {(r, c) | r > c}
- 對角線：D = {(r, c) | r = c}
對角線 D 就是所有沒被覆蓋的格子，
我們的任務就是用矩形把 U 和 L 都蓋滿，不能重疊，也不能漏。
---
先看上半部 U。
對每個 k = 1, 2, …, n−1，我們設一塊矩形：
Tk = {(r, c) | 1 ≤ r ≤ k, k+1 ≤ c ≤ n}。
這塊 Tk 覆蓋了前 k 行、從第 k+1 列開始的格子。
所以：
- T1 蓋第一行的右邊部分；
- T2 蓋前兩行的後段；
- T3 蓋前三行更靠右的區域；
如此一路下去。
這些矩形就像一階一階的「階梯」，剛好鋪滿上三角形區域 U。
它們彼此不重疊，完全填滿 U。
然後，用對稱的方式處理下半部：
對每個 k = 1, 2, …, n−1，
定義
T′k = {(r, c) | n−k+1 ≤ r ≤ n, 1 ≤ c ≤ n−k}。
這些就是下半部的鏡像矩形，
同樣互不重疊，正好覆蓋整個 L。
---
上半部有 n−1 塊，下半部也有 n−1 塊，
它們沿著對角線接觸但不重疊，
所以總數是：
(n−1) + (n−1) − 1 = 2n − 3。
這個 −1 是因為重疊在邊界的那條「線」不算新磁磚。
---
為什麼這是最少的？
如果想少用一塊，勢必會造成某一整行或整列出現兩格空白，
那就違反了「每行每列剛好一格未覆蓋」的條件。
因此 2n−3 已經是最小可能。
---
代入 n = 2025
T_min = 2 × 2025 − 3 = 4047。
Answer：4047
