→ hala932:消除用遞迴做也只要O(n) 你的作法比較複雜也沒比較快 12/15 03:16
→ hala932:至少你第一步求現有的短棒就需要O(n) 12/15 03:18
※ 引述《boyen3 (Mentirosa!!)》之銘言：
: 之前也交過俄羅斯方塊當作業
: 我的想法是這樣:
: 先看範圍要多大 用一個二維陣列表示
: 數值用 0:代表那一格沒有方塊
: 1:代表那一格有方塊
: 一直更新陣列值 值是1的地方 看要用什麼東西代表貼上去就可以了
: 然後大概有幾個要注意的地方:
: 方塊移動 變形 滿行消除 邊界 碰撞判斷 下降速度
: 大概都很好處理 但是弄起來很煩...
:
: 原po學校真拼
我還沒有實作~ 我大概設計了一下
我覺得關鍵點兩個部份:
1. 變型(這個預structure描述方塊可能得轉向 不過我忘了...)
2. 整行消除(其實這個要硬作最簡單...)
---------------------------------------
先談2. 整行消除 就方塊碰撞後 直接Scan 整條row
連續檢查 是不是都有 block存在即可
不過 我的想法是
使用 pair<int,int> 做成 "短棒" (左邊界,右邊界)
然後用 list<> 來串 每次insert入list 進行短棒"融合"
ex: 某行如下
## ## ###
0123456789
其中存在短棒 (0,1)(3,4)(7,9)
他的list會形如
(0,1)->(3,4)->(7,9)
當一個block 插入2的位置 把 (2,2) insert into list<> 後變成
(0,4)->(7,9)
這樣的話 就可以... 節能減炭...
說真得 這個方法除了implement較有難度
大量的mem alloc 似乎沒有多省能...
變型的部分 我再找一下 我記得我有描述方塊動作的草圖...
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.112.129
※ 編輯: softwind 來自: 118.166.112.129 (12/15 01:03)