পাইথনে অক্ষরের ম্যাট্রিক্স থেকে আমরা তৈরি করতে পারি এমন শব্দের সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের কাছে একটি 4 x 4 বর্ণের বোর্ড এবং শব্দের একটি তালিকা রয়েছে, আমাদের প্রতি শব্দে সর্বাধিক একবারে একটি ঘর ব্যবহার করে সংলগ্ন অক্ষরগুলির একটি ক্রম দ্বারা বোর্ডে তৈরি করা যেতে পারে এমন সর্বাধিক সংখ্যক শব্দ খুঁজে বের করতে হবে (কিন্তু আমরা অন্য শব্দের জন্য কোষ পুনরায় ব্যবহার করতে পারেন)। আমরা উপরে, নীচে, বাম, ডান বা তির্যক দিকে যেতে পারি।

সুতরাং, যদি ইনপুট মত হয়

m	b	f	d
x	a	y	a
t	z	t	r
s	q	q	q

শব্দ =["ব্যাট", "দূর", "ম্যাট"], তাহলে আউটপুট হবে 3, যেমন আমরা ম্যাট তৈরি করতে পারি [0,1] → [1,1] → [2,0], ব্যাট [0, 2] → [1,1] → [2,2], এবং দূর [0,2] → [1,3] → [2,3]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

N :=A এর সারি গণনা, M :=A এর আকারের কলাম গণনা
trie :=একটি নতুন মানচিত্র
প্রতিটি শব্দের জন্য, করুন
- বর্তমান :=চেষ্টা করুন
- প্রতিটি c শব্দের জন্য, করুন
  - যদি সি কারেন্টে থাকে, তাহলে
    - বর্তমান :=বর্তমান[c]
  - অন্যথায়,
    - বর্তমান [c] :=একটি নতুন মানচিত্র
    - বর্তমান :=বর্তমান[c]
- বর্তমান["*"] :=সত্য
উত্তর :=0
একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি x, y, d
লাগবে
যদি "*" d তে থাকে, তাহলে
- d["*"]
  সরান
- ans :=ans + 1
temp :=A[x, y]
A[x, y] :="#"
প্রতিটি আইটেমের জন্য আমি [x - 1, x, x + 1], do
- [y - 1, y, y + 1]-এ প্রতিটি আইটেমের জন্য j, করুন
  - যদি ম্যাট্রিক্সের পরিসরে i এবং j এবং A[i, j] d হয়, তাহলে
    - dfs(i, j, d[A[i, j]])
A[x, y] :=temp
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
i 0 থেকে N রেঞ্জের জন্য, করুন
- 0 থেকে M পরিসরে j-এর জন্য করুন
  - যদি A[i][j] চেষ্টা করা হয়, তাহলে
    - dfs(i, j, trie[A[i, j]])
উত্তর ফেরত দিন

উদাহরণ (পাইথন)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

class Solution:
   def solve(self, A, words):
      N = len(A)
      M = len(A[0])
      trie = dict()
      for word in words:
         current = trie
         for c in word:
            if c in current:
               current = current[c]
            else:
               current[c] = dict()
               current = current[c]
         current["*"] = True
      ans = 0
      def dfs(x, y, d):
         nonlocal ans
         if "*" in d:
            del d["*"]
            ans += 1
         temp = A[x][y]
         A[x][y] = "#"
         for i in [x - 1, x, x + 1]:
            for j in [y - 1, y, y + 1]:
               if 0 <= i < N and 0 <= j < M and A[i][j] in d: dfs(i, j, d[A[i][j]])
         A[x][y] = temp
      for i in range(N):
         for j in range(M):
            if A[i][j] in trie:
               dfs(i, j, trie[A[i][j]])
      return ans
ob = Solution()
matrix = [
   ["m", "b", "f", "d"],
   ["x", "a", "y", "a"],
   ["t", "z", "t", "r"],
   ["s", "q", "q", "q"]
]
words = ["bat", "far", "mat"]
print(ob.solve(matrix, words))

ইনপুট

[
["m", "b", "f", "d"],
["x", "a", "y", "a"],
["t", "z", "t", "r"],
["s", "q", "q", "q"] ],
["bat", "far", "mat"]