作者fatcat8127 (胖胖貓)
看板Prob_Solve
標題[問題] APCS 20191026 P4
時間Thu Oct 31 21:51:07 2019
這題是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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1572529872.A.1D5.html
1F：推 ckc1ark: 如果只能從邊界刪 這範圍感覺可以dp 10/31 22:59
2F：推 oToToT: dp[u][d][l][r]代表最後矩形是(l,u)~(r,d)所需的最小步數 11/01 02:05
4F：→ fatcat8127: 謝謝大家的回覆，我自己想到priorty-queue 11/01 21:22
5F：推 DJWS: priority queue 要怎麼做？ 11/02 06:54
6F：→ fatcat8127: 把四個邊界的狀態丟到Heap，每次拿最小格子數的更新 11/02 10:46
8F：推 DJWS: 看起來是貪心法，我不太確定對不對 11/02 16:22
9F：推 DJWS: 噢我看懂了 這是Uniform-cost Search 結果是對的 11/02 16:31
10F：→ DJWS: #54-#56 少了大括號 11/02 16:32
11F：→ fatcat8127: 我習慣把相同事情用逗號併一起，那邊應該沒問題 11/04 08:38