পাইথনে বাইনারি ম্যাট্রিক্সে টপ-লেফট থেকে বটম-রাইটে পৌঁছানোর পথের সংখ্যা গণনা করার প্রোগ্রাম

একটি N x M বাইনারি ম্যাট্রিক্স দেওয়া আছে (০ = খালি সেল, ১ = ব্লকড সেল)। টপ-লেফট কোণা (০,০) থেকে শুরু করে বটম-রাইট কোণায় পৌঁছাতে কতটি পথ আছে সেটি বের করতে হবে। শুধু ডাউন এবং রাইট মুভ করা যাবে। উত্তর বড় হলে 10^9+7 দিয়ে মড করুন।

উদাহরণস্বরূপ,

matrix = [
  [0, 0, 1],
  [0, 0, 0],
  [1, 1, 0]
]

আউটপুট ২, কারণ দুটি পথ: Right, Down, Right, Down এবং Down, Right, Right, Down।

সমাধানের পদ্ধতি (ডাইনামিক প্রোগ্রামিং)

dp = ম্যাট্রিক্স আকারের ২D অ্যারে, সব ০।
dp[0][0] = 1।
প্রথম কলাম: i=1..n-1, যদি matrix[i][0]==1 ব্রেক, অন্যথায় dp[i][0]=1।
প্রথম সারি: j=1..m-1, যদি matrix[0][j]==1 ব্রেক, অন্যথায় dp[0][j]=1।
বাকি সেল: i=1..n-1, j=1..m-1:
- যদি matrix[i][j]==1, dp[i][j]=0।
- অন্যথায় dp[i][j] = dp[i-1][j] + dp[i][j-1]।
dp[-1][-1] রিটার্ন করুন।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, matrix):
        dp = [[0]*len(matrix[0]) for _ in range(len(matrix))]
        dp[0][0] = 1
        for i in range(1, len(matrix)):
            if matrix[i][0] == 1:
                break
            else:
                dp[i][0] = 1
        for j in range(1, len(matrix[0])):
            if matrix[0][j] == 1:
                break
            else:
                dp[0][j] = 1
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if matrix[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

ob = Solution()
matrix = [[0,0,1],[0,0,0],[1,1,0]]
print(ob.solve(matrix))

ইনপুট

matrix = [[0,0,1],[0,0,0],[1,1,0]]