NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2001高中組初賽
 NPSC 2001 高初 A.坦克任務

作者 主題: NPSC 2001 高初 A.坦克任務  (閱讀 630 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
NPSC 2001 高初 A.坦克任務
« 於: 五月 31, 2015, 05:24:11 pm »

現在有個想法,但不很確定:
因為敵砲最多只有4個,打掉或不打掉最多 2^4個狀況,各跑一次最短路徑
我預訂將地圖中原空白處的值改為0,而被敵砲威脅到的格子各加該敵砲值{1,2,4,8}
4個皆威脅到的最多+15、都沒威脅到的+0,當設定威脅或取消威脅 ± 該值
若某一格的值非0即不能通過,程式後補吧!
記錄

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
Re: NPSC 2001 高初 A.坦克任務
« 回覆 #1 於: 六月 15, 2015, 05:20:44 pm »

當初的想法應該有誤
本來想的比較單純,但要coding時愈看愈有問題,又剛好較忙,就放著
這兩天仔細看了一下,確定不行,但好像不容易哦!

炸掉敵方的炮臺順序不同也有不同的步數,所以新的想法如下

沒炸、炸1個、炸2個、炸3個、炸4個,全排列共65種各跑一次

而每跑一次的部份,找到要炸的砲臺的最短路徑s1+炸完後的最短路徑s2
▲ s2是將可炸掉砲臺的位置當起點來算
▲ 又剛炸完一個砲臺後需更新戰場的狀況(該砲臺位置不可走,其威脅的格子解除該砲的威脅,某些格仍會被其它砲威脅到哦)

程式碼好像要花點時間,但感覺有點方向了。

以上程式是假設戰場大小 1000x1000以內,較大可能就???
又如果戰場很小,例15x15也許可以另一種寫法吧
« 上次編輯: 六月 15, 2015, 05:27:38 pm 由 rscpp »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2001高中組初賽
 NPSC 2001 高初 A.坦克任務