前置技能

無

解說

對於衝 Run Time 排名其實是奧義級別的技巧。

我們時常在各種場合，需要用到 used：

  • BFS/DFS記錄是否走過
  • DP記錄是否有計算過
    …

通常的做法：
以 used[i][j] 記錄狀態 (i, j) 是否用過/走過
（視需要也可能只有一維，或需要更多維；在此以最常用的二維舉例）

bool used[N][N];
// 初始化
memset(used, 0, sizeof(used));
// 判斷是否用過
if (!used[i][j])
    ...
// 設為已用過
used[i][j] = true;

但是每次清空總是要花點時間，
而且我們每一組測資只需要記錄用過和沒用過，才兩種情況！

於是我們換個想法：
以 used[i][j] = k 記錄狀態 (i, j) 最後一次被用過/走過，是在第 k 組測資

// 單用 bool 不夠了，改用最快的 int；
// 利用 C 語言『全域變數必定被初始化成 0』的語言特性，省去一次 memset()
int used[N][N];
// 需要記錄目前是第幾組
int count = 0;
// 每組測資的「初始化」
++count;
// 判斷是否用過，只要看最後用過不是第 k 組，就是沒用過；之前哪組用過？誰管它！！
if (used[i][j] != count)
    ...
// 設為已用過
used[i][j] = count;

每一組測資 sizeof(used) 這麼多次的歸零初始化動作，
變成只要一個 ++count; 解決，其它幾乎不變