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.
This is a doughnut:
Here is another doughnut:
This is not a doughnut:
because the ones are not 4-connected and so can't surround anything.
Solution CommentsShow comments
Problem Recent Solvers18