計算數學 Problem Solving- 將零矩陣轉為特定矩陣

匿 匿名 626 次瀏覽 0 個回答

給定一個 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 囧 ▎ ●> ● ◤ ▌ ﹍﹍ 0 ▊囧> 幹...
▲ ■┘ ■ ▎ ■ █◤ ▌ ㄏ▋ ︶■
〈﹀ ∥ ▁▁∥ ▎ ﹀〉◤ ▋ ▊ 〈\ ψcockroach727

--

我要回答

0 個回答

還沒有人回答,你知道答案嗎?

我要回答

登入會員後即可回答問題。

免費註冊