[問題] 將零矩陣轉為特定矩陣

看板 Prob_Solve
作者
時間
留言 3則留言,3人參與討論
推噓 2  ( 2推 0噓 1→ )
給定一個 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://www.ptt.cc/bbs/Prob_Solve/M.1595808692.A.C94.html
1FLPH66: 你這個例子是 3 次吧, 全 1, 去上下改 2, 去左右改 2 07/27 14:55
2Fobelisk0114: 看起來應該可以只用 3 次 07/29 11:48
3Fexpiate: 我也是三次 08/06 16:07