মান লিজিয়ে দুটি অ্যারে আছে rowSum এবং colSum নন-নেগেটিভ ভ্যালু দিয়ে, যেখানে rowSum[i] হল i-তম রোয়ের এলিমেন্টগুলোর সম এবং colSum[j] হল j-তম কলামের সম। আমাদের একটি ম্যাট্রিক্স বের করতে হবে যেটির সাইজ (len(rowSum) x len(colSum)) এবং যেটি দেওয়া রো ও কলাম সম সেটিসফাই করে।
যেমন, ইনপুট হলে rowSum = [13,14,12], colSum = [9,13,17], তবে আউটপুট হবে:
| 9 | 4 | 0 |
| 0 | 9 | 5 |
| 0 | 0 | 12 |
সমাধানের ধাপসমূহ
matrix := খালি ম্যাট্রিক্সvisited := সেটminimum(r, c)ফাংশন ডিফাইন করুন:রো ও কলাম থেকে ন্যূনতম মান বের করুন, তার টাইপ (row/col) ও ইন্ডেক্স নোট করুন।
যদি টাইপ 'row' হয়, তবে সেটি ইনফিনিটিতে সেট করে কলামে মান বিয়োগ করুন।
যদি টাইপ 'col' হয়, তবে সেটি ইনফিনিটিতে সেট করে রোতে মান বিয়োগ করুন।
visited.add((index, type))
মেইন থেকে
len(visited) != len(r)+len(c)থাকা পর্যন্তminimum(r,c)কল করুন।matrixরিটার্ন করুন।
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন:
def solve(r, c):
matrix = [[0]*len(c) for _ in range(len(r))]
visited = set()
def minimum(r, c):
min_total = float('inf')
type = ''
for i in range(len(r)):
if r[i] < min_total:
index = i
type = 'row'
min_total = r[i]
for i in range(len(c)):
if c[i] < min_total:
min_total = c[i]
type = 'col'
index = i
if type == 'row':
r[index] = float('inf')
for i in range(len(c)):
if c[i] != float('inf') and c[i] >= min_total:
c[i] -= min_total
matrix[index][i] = min_total
break
if type == 'col':
c[index] = float('inf')
for i in range(len(r)):
if r[i] != float('inf') and r[i] >= min_total:
r[i] -= min_total
matrix[i][index] = min_total
break
visited.add((index, type))
while len(visited) != len(r) + len(c):
minimum(r, c)
return matrix
rowSum = [13,14,12]
colSum = [9,13,17]
print(solve(rowSum, colSum))ইনপুট
[13,14,12], [9,13,17]
আউটপুট
[[9, 4, 0], [0, 9, 5], [0, 0, 12]]
