作者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/cn.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