ধরুন, একটি ম্যাট্রিক্স mat দেওয়া আছে যাতে তিন ধরনের মান থাকে:
0= খালি জায়গা1= বোমা2= শত্রু
বোমা শুধু অনুভূমিক (horizontal) এবং লম্ব (vertical) দিকেই বিস্ফোরণ করে এক প্রান্ত থেকে অন্য প্রান্ত পর্যন্ত। আমাদের যাচাই করতে হবে যে সব শত্রু কি বোমা বিস্ফোরণে মারা যাবে।
যেমন, ইনপুট ম্যাট্রিক্স:
0 0 2 0 0 1 0 0 0 2 0 0 0 0 1 0আউটপুট হবে
True, কারণ [1,1]-এ থাকা বোমা [2,1]-এ থাকা শত্রুকে এবং [3,2]-এ থাকা বোমা [0,2]-এ থাকা শত্রুকে মেরে ফেলবে।
সমাধানের ধাপসমূহ
r = len(mat)(রো),c = len(mat[0])(কলাম)।- প্রতিটি সেল
(i, j)এর জন্য:- যদি
mat[i][j] == 1(বোমা) হয়:- সেই কলাম
j-এর সব সেল(x, j)যেটা বোমা নয়, সেগুলো0করুন (বিস্ফোরণ)۔ - সেই রো
i-এর সব সেল(i, y)যেটা বোমা নয়, সেগুলো0করুন।
- সেই কলাম
- যদি
- শেষে পুরো ম্যাট্রিক্স স্ক্যান করুন। যদি কোথাও
2(শত্রু) পাওয়া যায়, তবে False ফেরত দিন। - অন্যথায় True ফেরত দিন।
উদাহরণ কোড
def solve(mat):
r = len(mat)
c = len(mat[0])
for i in range(r):
for j in range(c):
if mat[i][j] == 1:
for x in range(r):
if mat[x][j] != 1:
mat[x][j] = 0
for y in range(c):
if mat[i][y] != 1:
mat[i][y] = 0
for i in range(r):
for j in range(c):
if mat[i][j] == 2:
return False
return True
matrix = [
[0,0,2,0],
[0,1,0,0],
[0,2,0,0],
[0,0,1,0]
]
print(solve(matrix))
ইনপুট
[ [0,0,2,0], [0,1,0,0], [0,2,0,0], [0,0,1,0] ]
আউটপুট
True
