Problem 502. Would Homer Like It?
Given a matrix of ones and zeros, you must determine if there are any doughnuts present (would Homer Simpson like it?). A doughnut is a 4-connected region of ones completely enclosing a 4-connected region of zeros. You can assume that any regions of ones are either blobs (or genus 0) or doughnuts (genus 1). Thus if you find any hole in a region of ones, it is a doughnut. Also, there are no nested doughnuts.
Return true if any doughnuts are present, otherwise false.
Examples:
This is a doughnut:
1 1 1
1 0 1
1 1 1
Here is another doughnut:
0 0 0 1 1 1
0 1 1 1 0 1
0 0 1 0 0 1
0 0 1 1 1 1
This is not a doughnut:
0 1 0
1 0 1
0 1 0
because the ones are not 4-connected and so can't surround anything.
Solution Stats
Problem Comments
-
4 Comments
Show
1 older comment
Ned Gulley
on 16 Mar 2012
Oh! Thanks for pointing that out. It will disappear again shortly. Sorry about that.
Alfonso Nieto-Castanon
on 16 Mar 2012
Sounds good (it was too easy this way)
Ned Gulley
on 19 Mar 2012
Okay, we should be back to no-toolbox coding.
Solution Comments
Show commentsProblem Recent Solvers18
Suggested Problems
-
1314 Solvers
-
Increment a number, given its digits
657 Solvers
-
343 Solvers
-
71 Solvers
-
853 Solvers
More from this Author50
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!