d173: 飛蛾撲火番外篇之楓火看電影

2021-08-01 00:59:55 +0800 CST Tags: math, puzzle, self-thinking-proof

出處：https://zerojudge.tw/ShowProblem?problemid=d173
提交：https://zerojudge.tw/Submissions?problemid=d173&account=allllllan123456

問題：給你一個 N * N 的棋盤，限制 $2 \le N\le 1000$，棋盤最左下格不放棋，最右上格放黑棋，其餘位置皆佈滿白棋，請問總共最少需要移動幾次棋子才能把起初置於最右上格的黑棋移動到最左下角？

　　　　　　　　　　　　　 $\Longrightarrow$ 最少移動次數 $\Longrightarrow$

解法：公式解為 $8N - 11$。

證明：通常離散數學的證明都挺有意思，為了推導方便，我們把棋盤轉換如下：

　　　　　　　　　　　　　 $\Longrightarrow$ 最少移動次數 $\Longrightarrow$

並重新定義移動規則，黑棋仍然是原本的黑棋，但是原本的無棋格用新的菱形棋代替，而原先的白棋則通通用無棋格代替。菱形棋可任意移動，但是黑棋必須和菱形棋交換位置才能移動。讀者可自行驗證這樣的新棋盤和原本的棋盤有一對一的對應。那現在的證明目標就轉移為在新棋盤底下的最少移動次數為 $8N - 11$。首先，黑棋第一步無論是要往左移或往下移，都必須先讓菱形棋移動到黑棋旁邊才行，不失一般性，統一先讓菱形棋移動到黑棋下方，菱形棋這回合的最少移動次數為 $N-1\ (水平方向) + N-2\ (垂直方向) = 2N-3$，接著讓

　　 $\Longrightarrow$ 菱形棋先向右移動 $N-1$ 步再向上移動 $N-2$ 步到黑棋的正下方 $\Longrightarrow$

黑棋和菱形棋交換才完成黑棋下移的動作。

　　　　　　　 $\Longrightarrow$ 讓黑棋和菱形棋交換才完成黑棋下移的動作 $\Longrightarrow$

接下來就是重頭戲了！在開始之前，有個很重要的引理必須先讓讀者知道。一旦菱形棋已經移動到黑棋旁邊了，那接下來每次黑棋的移動 (因為要透過和菱形棋交換的關係) 都會耗費 3 步或 5 步，圖示如下：

• Case 1 (黑棋左移)：　

• Case 2 (黑棋右移)：　

• Case 3 (黑棋下移)：　

　　　　　　　　　　　　其實這個 case 菱形棋要走右邊也是可以，但反正也是 5 步我就不列了。

那知道了上面這個引理之後，我們就可以來探討黑棋究竟該怎麼走才能達到最小步數。單就黑棋來說，它剛剛已經先下移一次了，易知它自己接下來必須還要至少下移 $N-2$ 步、左移 $N-1$ 步才能抵達終點，那麼我只要確保它在這過程中的每一步都是採取 3 步的 case，就能達到最小總步數，其實方法非常簡單，示意圖如下：

　 $\Rightarrow$ 3 步 $\Rightarrow$ $\Rightarrow$ 3 步 $\Rightarrow$ $\Rightarrow$ 。。。

$\hspace{5.2cm}$。。。 $\Rightarrow$ 3 步 $\Rightarrow$ $\Rightarrow$ 3 步 $\Rightarrow$

我們可以發現到只要讓黑棋隨時都走在對角線附近，那麼左移的時候就是 case 1，而下移的時候因為相對於菱形棋的方位是為右移所以是 case 2，如此一來就能讓每次黑棋移動的時候都是 3 步 case。最後步數總和即為 $(2N-3) + 1 + \Big(2(N-1)-1\Big)\cdot3 = 8N-11$。

1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5    int n;
6    while (cin >> n)
7        cout << 8 * n - 11 << '\n';
8    return 0;
9}