主題

ZeroJudge - e580: 00696 - How Many Knights　解題心得

Not In My Back Yard | 2019-12-28 23:30:42 | 巴幣 0 | 人氣 211

題目連結：

題目大意：

給定兩正整數 M 、 N （M 、 N ≦ 500，當 M ＝ N ＝ 0 時，代表輸入結束），代表一個有 M 列 N 行的西洋棋棋盤。試問該棋盤可以放置多少的騎士（knight，走法與象棋中的馬類似，都是往一方向走兩步、再從原本方向垂直的方向走一步）？

範例輸入：

2 3

5 5

4 7

0 0

範例輸出：

4 knights may be placed on a 2 row 3 column board.

13 knights may be placed on a 5 row 5 column board.

14 knights may be placed on a 4 row 7 column board.

解題思維：

當 M ＝ 1 或是 N ＝ 1 ，可以整排都放。

當 M ＝ 2 或是 N ＝ 2 ，可以四個四個放，每次放隔四格。如下（K 是騎士）：

__KK__KK__……

其他情況則是每個騎士放在各自的對角線，這個方法最多。如下：

_K_K_K_K_K_……

K_K_K_K_K_K……

_K_K_K_K_K_……

……

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。

ETH官方钱包