[問題] APCS 20191026 P4

[fatcat8127 (胖胖貓)]

這題是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
推 ckc1ark: 如果只能從邊界刪 這範圍感覺可以dp
推 oToToT: dp[u][d][l][r]代表最後矩形是(l,u)~(r,d)所需的最小步數
推 DJWS: https://hackmd.io/@wiwiho/HJwOGYb5r
→ fatcat8127: 謝謝大家的回覆，我自己想到priorty-queue
推 DJWS: priority queue 要怎麼做？
→ fatcat8127: 把四個邊界的狀態丟到Heap，每次拿最小格子數的更新
→ fatcat8127: https://ideone.com/cnIxLa
推 DJWS: 看起來是貪心法，我不太確定對不對
推 DJWS: 噢我看懂了 這是Uniform-cost Search  結果是對的
→ DJWS: #54-#56 少了大括號
→ fatcat8127: 我習慣把相同事情用逗號併一起，那邊應該沒問題