有一天,Dark Kingdom 發生地震,於是馬兒開始四處逃竄,為了防止王國珍貴的黑馬消失,DarkKnight 派他底下的士兵來擋住這些馬。
首先 DarkKnight 先用他的原力暫時讓這些馬停下來,但是馬實在太多了,不能維持很久,士兵們必須趁這段時間去卡住適當的位置,讓這些馬完全無法移動。
為了減輕士兵們的負擔,DarkKnight 在東北方放很多黑馬最喜歡的飼料,於是聞到飼料的馬就只會往東北方移動,這樣大大的減輕了士兵的負擔。
最後最重要的是,這些黑馬既然是 DarkKnight 飼養的,想必只會走馬步。
例如如果有一隻黑馬在(1,1)的位置, 有另一隻黑馬在(1,2)的位置(這在(1,1)的北方),然後另外有一個士兵在(3,2)的位置(這在(1,1)的東北方),那麼位在(1,1)的黑馬就不會移動了,因為(1,2)拐到馬腳,(3,2)又擋到路。
現在給你所有黑馬的位置,請問 DarkKnight 要讓所有黑馬無法移動,需要幾名士兵?
Sample Input | Sample Output |
8 1 1 2 2 3 3 4 4 1 3 3 1 2 4 4 2 |
6 |