Author |
Topic: Minimum lines to cover (Read 5520 times) |
|
bazinga
Junior Member
Gender: 
Posts: 53
|
 |
Minimum lines to cover
« on: Oct 15th, 2012, 10:06pm » |
 Quote  Modify
|
Given a 2-d array of 1' and 0's , give an algorithm to find minimum number of horizontal/vertical lines to cover all the zeros.
| hidden: |
For each position of zero check whether the number of 0's are greater in row or col. If row has more 0's draw one horizontal line otherwise if col has more 0's draw a vertical line. If 0's are equal in all rows and columns then arbitrarily break the tie.
Is this correct?
|
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Minimum lines to cover
« Reply #1 on: Oct 16th, 2012, 10:28am » |
Quote Modify
|
It doesn't give the optimal solution for
0 0 0
1 1 0
1 0 1
0 1 1
Three vertical lines will cover all zeroes, but if you start with a horizontal line (covering the greatest numbers of zeroes to start with), you still need three additional lines.
To start with, I'd look at each row/column that has only one 0, and then draw a line perpendicular through it. Because you need a line through that 0 anyway, and you may cross off extra ones this way. So it's a no-lose step. That doesn't provide a complete solution though.
Perhaps it'd work if, when you get stuck, you make a greedy choice (a line through most uncovered zeroes).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print