मान लीजिए, एक n x n मैट्रिक्स है जिसे 0 से आरंभ किया गया है। अब, एक सूची दी गई है जिसमें कुछ जोड़े हैं जिनमें एक विशेष पंक्ति और एक कॉलम स्थिति होती है। सूची में प्रत्येक आइटम i के लिए, उन सेल्स की सामग्री 1 से बढ़ जाती है जहां पंक्ति संख्या और कॉलम संख्या, सूची में आइटम i के पंक्ति मान और कॉलम मान से कम होती हैं। सभी सूची तत्वों को पार करने के बाद, हमें मैट्रिक्स में उन सेल्स की संख्या पता लगानी है जिनमें अधिकतम मान है। (पंक्ति और कॉलम इंडेक्स 0 से शुरू होते हैं)
तो, यदि इनपुट input_list = [[3, 5], [4, 6], [5, 3]] है, तो आउटपुट 9 होगा। मान लीजिए, यह एक 5 x 6 मैट्रिक्स है। पहले मैट्रिक्स में मान हैं
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
सूची के पहले तत्व को पार करने के बाद, यह बन जाता है:
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
सूची के दूसरे तत्व को पार करने के बाद, यह बन जाता है:
2 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 2 1 1 1 1 1 1 1 0 0 0 0 0 0
सूची के तीसरे तत्व को पार करने के बाद, यह बन जाता है:
3 3 3 2 2 1 3 3 3 2 2 1 3 3 3 2 2 1 2 2 2 1 1 1 1 1 1 0 0 0
मैट्रिक्स में अधिकतम मान 3 है, और 9 सेल्स हैं जिनमें यह मान है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- xpos := 0
- ypos := 0
- input_list में प्रत्येक item के लिए, करें
- यदि xpos, 0 के समान है, तो
- xpos := item[0]
- ypos := item[1]
- अन्यथा,
- xpos := (xpos, item[0]) का न्यूनतम
- ypos := (ypos, item[1]) का न्यूनतम
- यदि xpos, 0 के समान है, तो
- (xpos * ypos) लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
def solve(input_list): xpos = 0 ypos = 0 for item in input_list: if xpos == 0: xpos = item[0] ypos = item[1] else: xpos = min(xpos,item[0]) ypos = min(ypos,item[1]) return (xpos * ypos) print(solve([[3, 5], [4, 6], [5, 3]]))
इनपुट
[[3, 5], [4, 6], [5, 3]]
आउटपुट
9
