程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> 編程綜合問答 >> java-藍橋杯試題格子刷油漆,求思路

java-藍橋杯試題格子刷油漆,求思路

編輯:編程綜合問答
藍橋杯試題格子刷油漆,求思路

標題:格子刷油漆圖片說明

X國的一段古城牆的頂端可以看成 2*N個格子組成的矩形(如圖1所示),現需要把這些格子刷上保護漆。

你可以從任意一個格子刷起,刷完一格,可以移動到和它相鄰的格子(對角相鄰也算數),但不能移動到較遠的格子(因為油漆未干不能踩!)

比如:a d b c e f 就是合格的刷漆順序。

c e f d a b 是另一種合適的方案。

當已知 N 時,求總的方案數。當N較大時,結果會迅速增大,請把結果對 1000000007 (十億零七) 取模。

輸入數據為一個正整數(不大於1000)

輸出數據為一個整數。

例如:
用戶輸入:
2
程序應該輸出:
24

再例如:
用戶輸入:
3
程序應該輸出:
96

再例如:
用戶輸入:
22
程序應該輸出:
359635897

資源約定:
峰值內存消耗(含虛擬機) < 64M
CPU消耗 < 2000ms

最佳回答:


這個問題要反過來想不合理的情況。其實很簡單,只需要排除一種情況,就是有一列的兩個都被刷了,而前面還有未刷的,這樣就回不來了。比如例子中,如果c,d都被刷了,而a,b有一個或者兩個都未刷,這時候如果已經移動到了e,f列中,就無法返回a,b了,就完成不了了。也就是說,如果前面有未刷的,那麼就不能允許有一列的兩格都被刷。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved