作者obelisk0114 (追风筝的孩子)
看板Prob_Solve
标题[问题] 将零矩阵转为特定矩阵
时间Mon Jul 27 08:11:23 2020
给定一个 M x N 的零矩阵 (内部元素全为 0), 和一个函数 fn
fn(m1, m2, n1, n2, k) 是将这个矩阵的 submatrix :
m1 <= i <= m2, n1 <= j <= n2 的元素全部转为 k
需要呼叫最少几次这个函数, 才能将这个零矩阵转为 M x N 的目标矩阵 ?
第一个想法是用 BFS, 但是下一层不知道怎麽定义 ?
若是从最外围开始, 下面这个例子会有问题
1 2 2 2 2 1
2 2 2 2 2 2
2 2 2 2 2 2
1 2 2 2 2 1 需要呼叫 5 次, 先全部改 2, 再改 4 个顶点
--
肝不好 ▁▁ ● ◤
肝若好
人生是黑白的 ▏ ◤
考卷是空白的
▏ ◤
、 ﹐
● ●b 囧 ▎ ●> ● ◤
▌ ﹍﹍ ０ ▊囧＞
干...
▲ ■┘ ■ ▎ ■ █◤ ▌ ㄏ▋ ︶■
〈﹀ ∥ ▁▁∥ ▎ ﹀〉◤
▋ ▊ 〈\
ψcockroach727
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 73.83.225.250 (美国)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1595808692.A.C94.html
1F：推 LPH66: 你这个例子是 3 次吧, 全 1, 去上下改 2, 去左右改 2 07/27 14:55
2F：→ obelisk0114: 看起来应该可以只用 3 次 07/29 11:48
3F：推 expiate: 我也是三次 08/06 16:07