推 LPH66: 你這個例子是 3 次吧, 全 1, 去上下改 2, 去左右改 2 07/27 14:55
→ obelisk0114: 看起來應該可以只用 3 次 07/29 11:48
推 expiate: 我也是三次 08/06 16:07
給定一個 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