पायथन में बाइनरी ट्री कलरिंग गेम

मान लीजिए कि दो खिलाड़ी बाइनरी ट्री पर टर्न-आधारित गेम खेलते हैं। हमारे पास इस बाइनरी ट्री की जड़ है और ट्री में नोड्स की संख्या n है। यहां n विषम है, और प्रत्येक नोड का 1 से n तक का एक अलग मान है। सबसे पहले, पहला खिलाड़ी 1 <=x <=n के साथ एक मान x का नाम देता है, और दूसरा खिलाड़ी 1 <=y <=n के साथ एक मान y का नाम देता है और यह एक शर्त रखता है, जैसे कि y!=x। पहला खिलाड़ी नोड को मान x लाल रंग से रंगता है, और दूसरा खिलाड़ी नोड को y नीले रंग से रंगता है। उसके बाद, खिलाड़ी बारी-बारी से पहले खिलाड़ी से शुरुआत करते हैं। प्रत्येक मोड़ में, खिलाड़ी अपने रंग का एक नोड लेता है (खिलाड़ी 1 के लिए लाल, खिलाड़ी 2 के लिए नीला) और चुने हुए नोड (या तो बाएं या दाएं बच्चे, या लिए गए नोड के माता-पिता) के एक रंगहीन पड़ोसी को रंग देता है। अगर और केवल अगर कोई खिलाड़ी इस तरह से इस तरह के नोड नहीं ले सकता है, तो उन्हें अपनी बारी पास करनी होगी। यदि दोनों खिलाड़ी अपनी बारी पास करते हैं, तो खेल समाप्त हो जाएगा, और विजेता वह खिलाड़ी होता है जिसने अधिक नोड्स रंगे हैं।

मान लीजिए हम दूसरे खिलाड़ी हैं। यदि यह सुनिश्चित करने के लिए कि हम गेम जीतते हैं, ऐसे y को चुनना संभव है, तो सही लौटें। यदि यह संभव नहीं है, तो झूठी वापसी करें।

तो अगर पेड़ जैसा है -

और n 11 है और x 3 है, तो आउटपुट सही होगा, क्योंकि दूसरा खिलाड़ी मान 2 के साथ नोड ले सकता है

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• हल () नामक एक विधि को परिभाषित करें, यह नोड, एक्स, एल और आर लेगा, एल और आर शुरू में झूठे हैं, यह नीचे की तरह कार्य करेगा -

• यदि नोड मौजूद नहीं है, तो वापस आएं और बाहर निकलें

• यदि l सत्य है, तो बाएँVal को 1 से बढ़ाएँ, अन्यथा जब r सत्य है, तो दाएँVal को 1 से बढ़ाएँ

• यदि नोड मान x है, तो हल करें (नोड के बाएं, x, सत्य, असत्य) और कॉल हल करें (नोड का दायां, x, झूठा, सत्य)

• अन्यथा कॉल हल करें (नोड के बाएं, एक्स, एल, आर) और कॉल हल करें (नोड, एक्स, एल, आर के दाएं)

• मुख्य विधि इस प्रकार होगी -

• नोडटॉक्स:=0, लेफ्टवैल:=0, राइटवैल:=0

• कॉल सॉल्व (रूट, x, असत्य, असत्य)

• नोडटॉक्स :=n - लेफ्टवैल - राइटवैल - 1

• अस्थायी :=अधिकतम दायां वैल, नोडटॉक्स और लेफ्टवैल

• झूठी वापसी अगर (नोडटॉक्स + लेफ्टवैल + राइटवैल - (2 * अस्थायी)> =0), अन्यथा सत्य

उदाहरण (पायथन)

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def btreeGameWinningMove(self, root, n, x):
      self.nodeToX = 0
      self.leftVal = 0
      self.rightVal = 0
      self.solve(root,x)
      self.nodeToX = n - self.leftVal - self.rightVal - 1
      temp = max(self.rightVal,max(self.nodeToX,self.leftVal))
      return not (self.nodeToX + self.leftVal + self.rightVal - (2*temp)>=0)
   def solve(self,node,x,l= False,r = False):
      if not node:
         return
      if l:
         self.leftVal+=1
      elif r:
         self.rightVal+=1
      if node.data == x:
         self.solve(node.left,x,True,False)
         self.solve(node.right,x,False,True)
      else:
         self.solve(node.left,x,l,r)
         self.solve(node.right,x,l,r)
ob = Solution()
root = make_tree([1,2,3,4,5,6,7,8,9,10,11])
print(ob.btreeGameWinningMove(root, 11, 3))

इनपुट

[1,2,3,4,5,6,7,8,9,10,11]
11
3

आउटपुट

true