7
एन-बाय-एन बाइनरी मैट्रिक्स को ध्यान में रखते हुए, मैं दो आयताकारों का न्यूनतम क्षेत्र ढूंढना चाहता हूं जो सभी (1) को कवर करेंगे। यही है, आयत के क्षेत्रों का योग न्यूनतम होना चाहिए। आयताकार ओवरलैप कर सकते हैं।न्यूनतम क्षेत्र मैट्रिक्स
उदाहरण:
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
न्यूनतम क्षेत्र है: 3 * 9 + 9 * 3 = 54
मैं अगर वहाँ एक समाधान O(n^4) की तुलना में बेहतर पता करने के लिए इच्छुक हूँ।
क्या आप एक उदाहरण दे सकते हैं? – bragboy
यदि आवश्यक हो तो 0 भी कवर किया जा सकता है? – mbeckish