[問題] APCS 20191026 P4

看板 Prob_Solve
作者
時間
留言 11則留言,4人參與討論
推噓 6  ( 6推 0噓 5→ )
這題是APCS的題目, 所以我手上也沒有測資。 而題目是我憑藉記憶寫下來的, 如果有題意不清或是理解錯誤我可以補充。 給定一個二維陣列( 2<=(R,C)<=25 ), 每格的數值只會是0或1。 當同一行/列都是一樣的數值時便可以刪去這一行/列, 直到剩下一行或是一列時即結束。 題目詢問『最少』要變更幾格才可以讓給予的二維陣列不斷刪減達到停止條件? 刪減時必須遵守:刪減的格子只能從『現在範圍的邊界』中挑選! 測資的過程請參閱投影片:https://pse.is/KYPNP 題目說明: 範例輸入: 3 5 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 4 5 1 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 範例輸出: 1 2 測試輸入: 25 25 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 測試輸出: 288 --
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.217.144.2 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1572529872.A.1D5.html
1Fckc1ark: 如果只能從邊界刪 這範圍感覺可以dp 10/31 22:59
2FoToToT: dp[u][d][l][r]代表最後矩形是(l,u)~(r,d)所需的最小步數 11/01 02:05
3FDJWS: https://hackmd.io/@wiwiho/HJwOGYb5r 11/01 07:52
4Ffatcat8127: 謝謝大家的回覆,我自己想到priorty-queue 11/01 21:22
5FDJWS: priority queue 要怎麼做? 11/02 06:54
6Ffatcat8127: 把四個邊界的狀態丟到Heap,每次拿最小格子數的更新 11/02 10:46
7Ffatcat8127: https://ideone.com/cnIxLa 11/02 10:46
8FDJWS: 看起來是貪心法,我不太確定對不對 11/02 16:22
9FDJWS: 噢我看懂了 這是Uniform-cost Search 結果是對的 11/02 16:31
10FDJWS: #54-#56 少了大括號 11/02 16:32
11Ffatcat8127: 我習慣把相同事情用逗號併一起,那邊應該沒問題 11/04 08:38