[問題] 將零矩陣轉為特定矩陣
看板Prob_Solve (計算數學 Problem Solving)作者obelisk0114 (追風箏的孩子)時間4年前 (2020/07/27 08:11)推噓2(2推 0噓 1→)留言3則, 3人參與討論串1/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
推
07/27 14:55,
4年前
, 1F
07/27 14:55, 1F
→
07/29 11:48,
4年前
, 2F
07/29 11:48, 2F
推
08/06 16:07,
4年前
, 3F
08/06 16:07, 3F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
